Recursive and non-recursive C++ both 4ms


  • 54
    C

    Recursive

    TreeNode* invertTree(TreeNode* root) {
        if (root) {
            invertTree(root->left);
            invertTree(root->right);
            std::swap(root->left, root->right);
        }
        return root;
    }
    

    Non-Recursive

    TreeNode* invertTree(TreeNode* root) {
        std::stack<TreeNode*> stk;
        stk.push(root);
        
        while (!stk.empty()) {
            TreeNode* p = stk.top();
            stk.pop();
            if (p) {
                stk.push(p->left);
                stk.push(p->right);
                std::swap(p->left, p->right);
            }
        }
        return root;
    }

  • 0
    F

    Very smart! Thanks


  • -2
    P
     TreeNode* invertTree(TreeNode* root) {
        if(root) swap(invertTree(root->left),invertTree(root->right));
        return root;
    }
    

    I got complie error "no matching function for call to ‘swap(TreeNode*, TreeNode*)’".
    Can anyone explain this?


  • 0
    T

    Sorry for late reply but maybe useful for others. I think you should either be using namespace std or accessing swap by std::swap.


  • 0
    P

    swap(invertTree(root->left),invertTree(root->right)); // swap(TreeNode*, TreeNode*)
    but
    swap(root->left, root->right);// swap(TreeNode, TreeNode)

    compiler uses namespace std as default


  • 1
    I

    If swap without using std::swap, it costs 0ms.


  • 0
    L

    @peteraristo I think it may be because that the TreeNode* returned by invertTree is rvalue, but the function swap need the lvalue as input. Or when we use swap, we want to swap the value stored in the struct of root, but not just swap the value in template space.


  • 0
    P

    @ian34 Thank you so much, I was wondering why there are so many 0ms submits and non-recursive doesn't seem to make that much difference.


  • 0
    Y

    nice and elegant code,sometime it's necessary to write iterative code to get full understanding of recurrence.


  • 0
    N
    This post is deleted!

  • 0
    R

    Very nice!
    However, I make some change to the code, why the code cannot work
    class Solution {
    public:
    TreeNode* invertTree(TreeNode* &root) {
    if (root != nullptr) {
    TreeNode *l = invertTree(root->left);
    TreeNode *r = invertTree(root->right);
    std::swap(l, r);
    }
    return root;
    }

    };


  • 0
    C

    I wrote a recursive code similar to your solution. But I traversed the nodes in a preorder fashion rather than postorder manner. Runtime of preorder code is higher as compared to postorder . Can someone explain why?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.