Simple Recursion and Iteration (non-recursion) C++ solution


  • 0
    E

    The recursion version:

    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if (!root) return root;
            TreeNode * right_backup = root->right;
            root->right = invertTree(root->left);
            root->left = invertTree(right_backup);
            return root;
        }
    };
    

    The iteration version (using stack to simulate the recursion, with the same simple implementation (one loop, check the NULL node at the beginning of each "recursion", etc., to make it simple and clear)

    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if (!root) return root;
            stack<TreeNode*> s;
            s.push(root);
            while (!s.empty()) {
                TreeNode * probe = s.top();
                s.pop();
                if (!probe) continue;
                swap(probe->left, probe->right);
                s.push(probe->left);
                s.push(probe->right);
            }
            return root;
        }
    };
    

    Any words?


Log in to reply
 

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