Recursive and iterative solutions in C++,easy to understand


  • 2
    V

    Solution (1):

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

    or is OK:

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

    Solution (2):

    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if (root == NULL) return root;
            
            queue<TreeNode *>q;
            TreeNode *temp, *cur;
            
            q.push(root);
            while (!q.empty())
            {
                cur = q.front();
                q.pop();
                
                temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
                
                if (cur->left != NULL)
                    q.push(cur->left);
                if (cur->right != NULL)
                    q.push(cur->right);
            }
            
            return root;
        }
    };

Log in to reply
 

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