Invert Binary Tree: recursion là sự phù hợp tự nhiên

Tree là cấu trúc đệ quy. Một tree là một node có left subtree và right subtree, và mỗi subtree đó lại là một tree. Khi bạn đã hiểu điều đó, một bài toán như invert binary tree không còn là bài toán nữa. Nó đọc như một đặc tả: mirror node này, rồi mirror từng con. Code gần như là một bản phiên dịch trực tiếp.

Bài toán hỏi gì và constraints buộc bạn làm gì

Cho một tree có gốc là root, hoán đổi mọi left child với right child tương ứng tại mọi node, đi xuống tận cùng. Input [4,2,7,1,3,6,9] trở thành [4,7,2,9,6,3,1]. Root giữ nguyên; các subtree của nó hoán đổi; các subtree của những subtree đó cũng hoán đổi; và cứ thế tiếp tục.

Constraint set rất tối giản: tối đa 100 node, giá trị trong khoảng [-100, 100]. Không cái nào trong số đó đòi hỏi sự khéo léo nào cả. 100 node nghĩa là O(n²) vẫn ổn, O(n³) thậm chí có thể qua được. Không có áp lực về quy mô ở đây — bài toán hoàn toàn là về việc nhìn thấy cấu trúc.

Điều n <= 100 thực sự cho bạn biết: call stack depth tối đa là 100 frame, vì vậy recursive DFS không có rủi ro stack overflow. Đó là hậu quả thực tế duy nhất của constraint này: lập luận "dùng giải pháp iterative để tránh stack overflow", hợp lệ với tree có độ sâu 10,000, đơn giản là không áp dụng ở đây. Chọn giữa recursive và iterative là câu hỏi về sự rõ ràng, không phải về tính đúng đắn.

Các giá trị [-100, 100] không liên quan đến thuật toán. Giá trị node không bao giờ ảnh hưởng đến inversion; chúng ta chỉ động đến pointer.

Các keyword nên kích hoạt pattern này: "invert", "mirror", "flip", hoặc "reverse" một tree. Bất kỳ khi nào bạn thấy các thao tác đối xứng hay phản chiếu trên mọi node trong binary tree, bạn đang nhìn vào đúng hình dạng này.

Approach 1: Recursive DFS — O(n) time, O(h) space

Giải pháp đệ quy chỉ có ba dòng logic thực sự.

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

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

Base case: null node nghĩa là không có gì để invert — return ngay. Recursive case: hoán đổi các con, rồi đệ quy vào từng cái. Return root để pointer ban đầu vẫn hợp lệ.

Thứ tự thao tác có một chút quan trọng. Bạn hoán đổi trước, rồi mới đệ quy vào những gì bây giờ là các con đã hoán đổi. Cả hai thứ tự đều cho ra tree đúng vì bạn đang invert toàn bộ subtree bất kể sao — nhưng hoán đổi trước khi đệ quy làm mental model rõ hơn: node này xong rồi, giờ đi fix những gì nó trỏ tới.

Trace từng bước qua ví dụ chính

Input: [4,2,7,1,3,6,9]

Call stack diễn ra như sau:

Gọi invertTree(4)

• Hoán đổi: root.left=2, root.right=7 -> sau hoán đổi: root.left=7, root.right=2
• Push recursive call vào 7 (bây giờ là left child)

Gọi invertTree(7)

• Hoán đổi: root.left=6, root.right=9 -> sau hoán đổi: root.left=9, root.right=6
• Push recursive call vào 9

Gọi invertTree(9) - không có con, return null cho cả hai phía, return 9

Gọi invertTree(6) - không có con, return null cho cả hai phía, return 6

Quay lại invertTree(7): cả hai con xong, return 7

Gọi invertTree(2) (bây giờ là right child của root)

• Hoán đổi: root.left=1, root.right=3 -> sau hoán đổi: root.left=3, root.right=1
• Cả hai con là lá, recursion kết thúc ngay

Quay lại invertTree(4): cả hai con đã được invert đầy đủ, return 4

Kết quả:

Mỗi node được visit đúng một lần. Mỗi lần visit là O(1). Tổng cộng: O(n) time, O(h) space cho call stack với h là chiều cao của tree. Worst case với tree lệch hoàn toàn là O(n). Tree cân bằng cho O(log n).

Tại sao recursion là sự phù hợp tự nhiên

Khi bạn thấy một bài toán tree, hãy hỏi: câu trả lời cho node này có phụ thuộc vào câu trả lời từ các con của nó không? Nếu có, recursion gần như luôn là hình dạng đúng.

Với invert: phiên bản inverted của một node là node đó với các con đã hoán đổi, trong đó mỗi con đã hoán đổi cũng đã được invert. Định nghĩa này mang tính tuần hoàn đúng theo cách recursion xử lý. Bạn không tính toán gì phức tạp ở mỗi node — bạn chỉ hoán đổi hai pointer. Rồi bạn để các recursive call xử lý phần còn lại, tin tưởng rằng chúng tuân theo cùng quy tắc.

Đây là điều người ta muốn nói khi họ nói recursion "rút gọn bài toán thành các subproblem cùng hình dạng." Các subproblem ở đây theo nghĩa đen là cùng bài toán trên một tree nhỏ hơn. Base case (null) kết thúc chuỗi.

Trong một buổi interview tôi sẽ viết phiên bản này ngay lập tức. Nó ngắn, đúng, và truyền đạt cấu trúc của thuật toán một cách trực tiếp.

Approach 2: Iterative BFS — O(n) time, O(w) space

Nếu bạn muốn giải pháp iterative, BFS với queue là tự nhiên nhất. Xử lý node theo từng level; tại mỗi node, hoán đổi các con và enqueue chúng.

from collections import deque
 
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            (node.left, node.right) = (node.right, node.left);
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        return root;
    }
}

Đi qua cùng ví dụ — lần này theo từng level:

queue = [4]

Iteration 1: pop 4, hoán đổi con (2 <-> 7), enqueue [7, 2]
Iteration 2: pop 7, hoán đổi con (6 <-> 9), enqueue [2, 9, 6]
Iteration 3: pop 2, hoán đổi con (1 <-> 3), enqueue [9, 6, 3, 1]
Iterations 4-7: pop các lá 9, 6, 3, 1 — không có con để enqueue
queue rỗng, xong

Thứ tự visit node khác với DFS — bạn xử lý tree theo từng level — nhưng bạn vẫn visit mỗi node đúng một lần và thực hiện một lần hoán đổi mỗi node.

Complexity: O(n) time — giống phiên bản đệ quy. O(w) space, với w là chiều rộng tối đa của tree (level rộng nhất). Với tree cân bằng hoàn hảo, đó là O(n/2) = O(n) ở level dưới cùng. Với tree lệch hoàn toàn, đó là O(1). Trong trường hợp trung bình, BFS dùng nhiều bộ nhớ hơn DFS trên bài này.

Phiên bản BFS tránh được call stack depth, đôi khi được trích dẫn là lý do để dùng nó. Với tree 100 node và constraint của LeetCode, stack overflow không phải lo ngại thực tế. Phiên bản iterative đúng và rõ ràng, nhưng tôi sẽ không dùng nó đầu tiên trên bài này.

Approach 3: Iterative DFS với explicit stack — O(n) time, O(h) space

Bạn có thể mirror recursive DFS theo cách iterative bằng một explicit stack. Logic giống nhau: pop một node, hoán đổi con của nó, push chúng vào.

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        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

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;
        var stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count > 0) {
            var node = stack.Pop();
            (node.left, node.right) = (node.right, node.left);
            if (node.left != null) stack.Push(node.left);
            if (node.right != null) stack.Push(node.right);
        }
        return root;
    }
}

Điều này tạo ra traversal theo dạng pre-order (gần đúng), nhưng thứ tự các node được visit không ảnh hưởng đến tính đúng đắn ở đây. Mỗi node được swap đúng một lần bất kể bạn visit theo depth-first hay breadth-first. Phiên bản stack và phiên bản queue đều hoạt động; chúng chỉ visit node theo các trình tự khác nhau.

Edge case và tại sao code xử lý được chúng

Ba trường hợp cần nêu rõ:

Tree rỗng (root = null): guard if not root / if (root == null) return ngay lập tức trong cả ba approach. Không có gì được enqueue hay push. Caller nhận lại null, đó là output đúng cho tree rỗng.

Node duy nhất (không có con): swap chạy (None, None = None, None trong Python — là no-op), và cả hai recursive call ngay lập tức chạm base case. Node trả về không thay đổi. Các biến thể BFS và stack không enqueue gì sau khi pop. Đúng trong cả ba.

Tree lệch hoàn toàn (một chuỗi 100 node, mỗi node chỉ có left child): recursion đi sâu 100 frame. Stack depth là O(n) thay vì O(log n). Với constraint của bài toán này thì là 100 frame — vô hại. Nếu constraint là n = 100,000, đây mới là lập luận cho iterative DFS; ở đây thì không.

Node chỉ có một con (ví dụ có left child, right là null): swap chạy đúng — (node, null) trở thành (null, node). Con không null được enqueue/push; phía null không bao giờ được (được guard bởi if node.left / if node.right). Không có gì bị hỏng.

Lỗi cổ điển: viết root.left = root.right; root.right = root.left mà không có biến temp. Dòng thứ hai đọc lại root.left đã bị ghi đè, vì vậy cả hai phía đều kết thúc trỏ đến right child ban đầu. Trong Python, tuple unpacking (a, b = b, a) đánh giá phía phải trước bất kỳ phép gán nào. Trong C#, cú pháp deconstruction (a, b) = (b, a) cũng làm vậy. Trong các ngôn ngữ không có shorthand nào — Go, Java với swap thủ công — luôn dùng biến temp.

Cái nào để viết

Đệ quy. Mọi lần, trên bài này.

Recursion làm cấu trúc của giải pháp hiện rõ. Một người đọc có thể thấy ngay lập tức rằng thuật toán là: làm điều này ở root, rồi làm điều tương tự ở mỗi con. Các phiên bản iterative che khuất điều đó sau một vòng lặp và một cấu trúc dữ liệu phụ trợ. Chúng không sai — nhưng chúng là mô tả kém hơn về những gì thực sự đang xảy ra.

Lập luận duy nhất cho phiên bản iterative là tránh call stack sâu. Trên bất kỳ tree nào bạn gặp trong interview hay trên LeetCode, đó không phải lo ngại thực tế. Nếu ai đó đề cập đến nó, bạn có thể thừa nhận và sau đó chỉ ra rằng với bài cụ thể này, trên input thực tế, phiên bản đệ quy ưu việt hơn hoàn toàn về mặt readability.

Complexity của cả ba approach

Cả ba đều O(n) time. Sự khác biệt về space là có thật nhưng nhỏ trong thực tế — và với hầu hết các tree, O(h) và O(w) nằm trong một constant factor của nhau. Sự bất đối xứng về space đảo chiều tùy thuộc vào hình dạng tree: BFS tốt hơn trên tree lệch, DFS tốt hơn trên tree cân bằng hoàn hảo.

Các bài liên quan

Maximum Depth of Binary Tree (104) là bước tiếp theo tự nhiên trong series này. Nó dùng cùng skeleton đệ quy: tại mỗi node, hỏi cả hai con về depth của chúng, lấy max, cộng một. Pattern là "đệ quy vào cả hai con và kết hợp kết quả" — invert dùng cùng cấu trúc nhưng bỏ qua giá trị return của các recursive call (chúng ta chỉ quan tâm đến side effect, không phải tổng hợp một giá trị).

Symmetric Tree (101) là câu hỏi ngược — không sửa đổi tree mà kiểm tra xem nó đã trông như ảnh mirror của chính nó chưa. Recursion so sánh left.left với right.right và left.right với right.left đồng thời. Nếu bạn thấy cấu trúc đệ quy của inversion rõ ràng, symmetry check sẽ cảm thấy quen thuộc — đó là cùng hình dạng traversal, nhưng chỉ đọc.

Binary Tree Level Order Traversal (102) là nơi BFS xứng đáng với vị trí của mình. Level-order traversal là bài mà BFS queue là sự phù hợp tự nhiên vì bạn cần nhóm các node theo độ sâu — điều DFS không thể cho bạn một cách gọn gàng. Sau invert, đáng để xem một bài mà BFS iterative là công cụ đúng theo sự cần thiết thay vì tùy chọn.

Same Tree (100) dùng cấu trúc recursive comparison tương tự. Ghép với Symmetric Tree cho bạn hai ví dụ liên tiếp về việc so sánh hai tree (hoặc một tree với chính nó) dùng DFS, xây dựng khả năng nhận diện pattern cho khi DFS là lựa chọn đúng về mặt cấu trúc.