Invert Binary Tree

Câu chuyện huyền thoại

Max Howell (tác giả của Homebrew - công cụ mà 90% kỹ sư dùng Mac đều cài) từng chia sẻ trên Twitter rằng anh bị Google từ chối vì không làm được bài này trên bảng trắng:

"Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off."

Thực tế, bài này rất dễ nếu bạn hiểu về đệ quy.

Bài toán

Cho root của một cây nhị phân. Hãy đảo ngược cây (như soi gương) và trả về root.

• Cây con bên trái đổi chỗ sang phải.
• Cây con bên phải đổi chỗ sang trái.
• Đệ quy xuống các node con.

Ví dụ:

Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Phân Tích & Tiếp Cận

Đệ quy (DFS)

Tại mỗi Node, việc cần làm là:

1. Đổi chỗ (Swap) hai con left và right của nó.
2. Ra lệnh cho con left (lúc này là con cũ ở bên phải): "Hãy tự đảo ngược bản thân ngươi đi". (invert(node.left))
3. Ra lệnh cho con right (lúc này là con cũ ở bên trái): "Ngươi cũng thế". (invert(node.right))

Base Case: Nếu node là null -> Không làm gì cả.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) {
        return null; // Base case
    }

    // Swap
    const temp = root.left;
    root.left = root.right;
    root.right = temp;

    // Recursion
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

• Time Complexity: $O(n)$ - Mỗi node được ghé thăm 1 lần.
• Space Complexity: $O(h)$ - Chiều cao cây (Call Stack).

Pattern Nhận Diện

Hầu hết bài toán về Tree đều giải bằng Đệ Quy (Recursion). Tư duy: "Nếu tôi giải quyết được vấn đề tại Node hiện tại và giả sử 2 con của tôi đã làm xong việc của chúng, thì tôi cần làm gì?".