Invert a Binary Tree

easy tree dfs

Problem

Replace every node's left subtree with its right subtree (and vice versa). The result is the mirror image of the original tree.

One DFS does the job: at each node, swap its two child links, then recurse into both children. The order (top-down vs bottom-up) doesn't matter for correctness.

Input"4, 2, 7, 1, 3, 6, 9"

Output"4, 7, 2, 9, 6, 3, 1"

tree (level-order, '_' for null)

def invert(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    invert(node.left)
    invert(node.right)
    return node

function invert(node) {
  if (!node) return null;
  const tmp = node.left;
  node.left = node.right;
  node.right = tmp;
  invert(node.left);
  invert(node.right);
  return node;
}

class Solution {
    public TreeNode invert(TreeNode node) {
        if (node == null) return null;
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        invert(node.left);
        invert(node.right);
        return node;
    }
}

TreeNode* invert(TreeNode* node) {
    if (!node) return nullptr;
    swap(node->left, node->right);
    invert(node->left);
    invert(node->right);
    return node;
}

Time: O(n) Space: O(h)