Invert Binary Tree


  • 0

    Click here to see the full article post


  • 0
    J

    Approach #3
    In order traversal of the given tree.
    Store the traversed elements in a stack (or a array and reverse the array)
    Build a binary tree with the midpoint approach with the above stack or reversed array


  • 0
    J

    @justanotherbring The key to note is tha inverted tree order is the reverse of the order traversal of of the existing tree .


  • 0
    V

    For the Iterative solution, we can use Stack also to store the children & swap their children. I wrote the below code in C#.

    BinTreeNode InvertBinaryTreeIterative(BinTreeNode root)
            {
                if (root == null)
                    return null;
    
                Stack<BinTreeNode> st = new Stack<BinTreeNode>();
                st.Push(root);
    
                while (st.Count > 0)
                {
                    BinTreeNode node = st.Pop();
                    BinTreeNode temp = node.Left;
                    node.Left = node.Right;
                    node.Right = temp;
    
                    if (node.Left != null)
                        st.Push(node.Left);
                    if (node.Right != null)
                        st.Push(node.Right);
                }
    
                return root;
            }
    

  • 0
    S

    My shorter Java code:

    public class Solution {
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode temp = root.left;
            root.left = invertTree(root.right);
            root.right = invertTree(temp);
            return root;
        }
    }
    

  • 0
    B

    I was doing this :

    TreeNode* invertTree(TreeNode* root) {
            if (root == NULL) return NULL;
            if (root -> left == NULL && root -> right == NULL) return root;
                    
            invertTree(root -> left);
            invertTree(root -> right);
            
            TreeNode *temp = root -> left;
            root -> left = root -> right;
            root -> right = root -> left;
    
            return root;
    }
    

    It's giving me runtime error. can anyone suggest what i am doing wrong?


  • 0
    I

    javascript

    var invertTree = function(root) {
        if (!root)
            return null;
            
        // recursive
        invertTree(root.left);
        invertTree(root.right);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // iterative
        // var queue = [];
        // queue.unshift(root);
        // while(queue[0]){
        //     current = queue.pop();
        //     temp = current.left;
        //     current.left  = current.right;
        //     current.right = temp;
        //     if(current.left) queue.unshift(current.left);
        //     if(current.right) queue.unshift(current.right);
        // }
        
        return root;
    };
    

  • 0
    P

    python:

    Solution(object):
        def invertTree(self, root):
            if(root == None): return
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
    

  • 0
    R

    go:

    func invertTree(root *TreeNode) *TreeNode {
        if root == nil {
            return nil
        }
        root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
        return root
    }
    

  • 0
    F
    const invertTree = root => root 
    ? Object.assign(new TreeNode(root.val), {
        left: invertTree(root.right), 
        right: invertTree(root.left)
      })
    : null
    

  • 0
    C

    C

    struct TreeNode* invertTree(struct TreeNode* root) {
        struct TreeNode     *tmp;
        if (root) {
            tmp = invertTree(root->left);
            root->left = invertTree(root->right);
            root->right = tmp;
        }
        return root;
    }
    

  • 0
    S
      public TreeNode InvertTree(TreeNode currentNode)
        {
            if (currentNode == null)
                return null;
    
            TreeNode rightNode = InvertTree(currentNode.right);
            TreeNode leftNode = InvertTree(currentNode.left);
    
            currentNode.left = rightNode;
            currentNode.right = leftNode;
    
            return currentNode;
        }

  • 0
    S

    Conciseness of Python

            if root != None:
                root.left, root.right = root.right, root.left
                map(self.invertTree, (root.left, root.right))
            return root
    

  • 0
    F

    Haskell

    Assuming Tree is presented similar to this

    data Tree a = Empty | Node (Tree a) a (Tree a) deriving (...)
    
    invertTree :: Tree a -> Tree a
    invertTree Empty = Empty
    invertTree (Node left n right) = Node (invertTree right) n (invertTree left)
    

  • 0
    J

    Simple Recursion
    public class Solution {
    public TreeNode invertTree(TreeNode root) {

        if(root == null) return null;
        TreeNode newR = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(newR);
        
        return root;
    }
    

    }


  • 0
    A

    @baila There is a simple mistake in the swap. Since you changed root->left, so root->right should be assigned to temp.

    TreeNode *temp = root -> left;
    root -> left = root -> right;
    root -> right = temp;

    Your solution is perfectly fine with this change.


  • 0
    A
                 if (root == null){
                return root;
            }
    
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
    
            invertTree(root.left);
            invertTree(root.right);
    
            return root;
    

    i think this is more eaiser to understand


  • 0
    D

    What if there is only one root without left of right node?Or only has right or only left tree?
    May consider NullPointerException?


  • 0
    D

    sorry,forget what I've said..


  • 0
    W

    public TreeNode invertTree(TreeNode root) {
    if (root != null){
    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    }
    return root;
    }


Log in to reply
 

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