0226. Invert Binary Tree

Easy | Tree + Recursion / Stack | 16 ms (99.96%), 14 MB (90.10%)

❓ Problem Statement

Source: LeetCode - Invery Binary Tree GitHub: Solution / Performance

Given the root of a binary tree, invert the tree, and return its root.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

💡 Ideas

Swap left- and right-pointer in each iteration.

​ 🤖 Python3

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # (base case)
        if (not root) or (not root.left and not root.right): return root
        
        # ==================================================
        #  Binary Tree                       (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [root]
        while stack:
            node = stack.pop()
                
            node.left, node.right = node.right, node.left
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            
        return root
            
        '''
        # ==================================================
        #  Tree                              (Recursive)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */

    public TreeNode invertTree(TreeNode root) {
        if((root == null) || (root.left == null && root.right == null)) return root;
        
        TreeNode tmp = root.left;
        root.left  = root.right;
        root.right = tmp;
           
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}