Accepted C++ solution both Recursive and non-recursive


  • 6
    N

    Recursive:

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

    non-recursive:

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

  • 0
    C

    one question, why do we need the following:

    if(root == NULL)
    return root;

    we are already checking if root->left or root->right is NULL, and only calling the function if thy exist.

    Thanks.


  • 0
    N

    If the input tree is an empty tree


  • 0
    Q
    if(root->left == NULL && root->right == NULL)
    

    there is another way to express same meaning ;)

    if(root->left==root->right)
    

Log in to reply
 

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