💬 Discord
Sign In
NeetCode #386LC-226EasyTreesBlind 75NC 150NC 250
← Back to All Problems

#386 · #226 · Invert Binary Tree(翻转二叉树)

📌 Problem Statement & Constraints

Given the root of a binary tree, invert it (swap every node's left and right children) and return its root. Constraints: the number of nodes is in [0, 100], -100 <= Node.val <= 100.

💡 Core Algorithmic Approaches

  1. Recursively invert both subtrees, then swap the two results into place.
  2. The base case is a None node, which returns None.
  3. Python's tuple assignment performs the swap and the recursive calls in one line, and the right-hand side is fully evaluated before any assignment.
  4. Any traversal order works; an iterative BFS/DFS is an equivalent alternative.

💻 Benchmark Python3 Implementation

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        # evaluate both recursive calls before assigning, then swap
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root


# Iterative BFS variant
class Solution2:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        from collections import deque
        if not root:
            return None
        q = deque([root])
        while q:
            node = q.popleft()
            node.left, node.right = node.right, node.left   # swap
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(h) for the recursion stack (h is the tree height), or O(n) for the BFS queue in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping before recursing without saving a child: root.left = invert(root.right) then root.right = invert(root.left) uses the already-overwritten left child. The tuple assignment avoids this.
  • Forgetting the None base case: the recursion would raise an AttributeError.
  • Assuming the tree is balanced: the recursion depth can reach n for a degenerate tree, which matters for very deep inputs.
  • Returning the original root unchanged: the inversion must be applied.