Same Tree: hai cây, một câu hỏi đệ quy

Hai binary tree giống hệt nhau khi và chỉ khi mọi cặp node tương ứng có cùng giá trị và cùng vị trí cấu trúc. Chỉ vậy thôi. Bài toán yêu cầu đi song song qua hai cây và thất bại ngay khi phát hiện bất kỳ sự khác biệt nào — một null ở chỗ đáng ra có giá trị, hai giá trị không khớp, một node con tồn tại ở cây này nhưng không có ở cây kia.

Cách đọc cấu trúc rất tự nhiên: kết quả của isSameTree(p, q) là true nếu hai node hiện tại bằng nhau và cả isSameTree(p.left, q.left) lẫn isSameTree(p.right, q.right) đều trả về true. Recursion kết thúc tại các null node. Code gần như tự viết ra.

Constraints nói gì trước khi bạn viết một dòng

Giới hạn bài toán là [0, 100] node và giá trị trong [-10⁴, 10⁴]. Không có gì ở đây đòi hỏi sự khéo léo đặc biệt.

100 node nghĩa là bạn có thể dùng recursion mà không lo stack overflow — giới hạn recursion mặc định của Python là 1000, và độ sâu call tối đa ở đây là 100 (chuỗi lệch hoàn toàn về trái hoặc phải). Không có trường hợp nào trong giới hạn này buộc bạn phải dùng iterative để tránh crash. Giải pháp BFS không phải vì lý do an toàn; nó là một chiến lược duyệt cây thay thế.

Dải giá trị [-10⁴, 10⁴] bao gồm số âm và số 0, điều quan trọng là không được coi 0 là sentinel. Luôn so sánh p.val != q.val trực tiếp — đừng giả định 0 nghĩa là rỗng.

Trường hợp không có node (n = 0) nằm trong phạm vi hợp lệ. Cả hai cây đều có thể là null. Đây không phải edge case cần xử lý phức tạp — nó rơi vào base case đầu tiên một cách tự nhiên.

Approach 1: Recursive DFS — ba base case, sau đó recurse

Phiên bản đệ quy ngắn gọn như một bài toán cây có thể đạt được.

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return (self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

Thứ tự các base case rất quan trọng. Kiểm tra cả hai null trước — đó là điều kiện kết thúc thành công. Sau đó kiểm tra một bên null — cấu trúc không khớp. Rồi mới kiểm tra giá trị. Nếu bạn kiểm tra giá trị trước các null check, bạn sẽ dereference null trong trường hợp cấu trúc không khớp.

Short-circuit evaluation làm việc thực sự hữu ích trong lời gọi đệ quy. Khi isSameTree(p.left, q.left) trả về false, and của Python / && của C# không đánh giá subtree phải nữa. Bạn được early exit miễn phí.

Trace tay qua Example 2: p = [1,2], q = [1,null,2]

Gọi isSameTree(p=1, q=1):

• Cả hai không null, giá trị bằng nhau (1 == 1) -> recurse vào con
• Gọi isSameTree(p=2, q=null):
  • p không null, q là null -> base case thứ hai kích hoạt, trả về false
• Subtree trái trả về false, and short-circuit
• Kết quả cuối: false

Hai cây có cấu trúc khác nhau: p có con trái, q thì không. Sự khác biệt cấu trúc xuất hiện ngay tại lời gọi subtree trái.

Time và space complexity

Time: O(min(m, n)) trong đó m và n là số node của hai cây. Trong trường hợp xấu nhất (hai cây giống hệt nhau), bạn thăm mọi node của cây nhỏ hơn. Khi bất kỳ cặp nào phân kỳ, bạn dừng lại — worst case vẫn là O(min(m, n)), nhưng thường bạn làm ít hơn.

Space: O(min(m, n)) cho call stack trong trường hợp xấu nhất. Chuỗi lệch hoàn toàn gồm 100 node tạo ra 100 stack frame. Cây cân bằng gồm 100 node có độ sâu tối đa khoảng 7 frame. Trong thực tế, dung lượng bộ nhớ được quyết định bởi chiều cao cây, không phải số node.

Approach 2: Iterative BFS — một shared queue cho hai cây

Thay vì recursion, bạn có thể xử lý cả hai cây đồng thời bằng queue. Mỗi phần tử trong queue chứa một cặp (node_từ_p, node_từ_q). Bạn dequeue một cặp, kiểm tra nó, rồi enqueue cả hai cặp con.

from collections import deque
 
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        queue = deque([(p, q)])
        while queue:
            node1, node2 = queue.popleft()
            if not node1 and not node2:
                continue
            if not node1 or not node2 or node1.val != node2.val:
                return False
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
        return True

using System.Collections.Generic;
 
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        var queue = new Queue<(TreeNode, TreeNode)>();
        queue.Enqueue((p, q));
        while (queue.Count > 0) {
            var (node1, node2) = queue.Dequeue();
            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null || node1.val != node2.val) return false;
            queue.Enqueue((node1.left, node2.left));
            queue.Enqueue((node1.right, node2.right));
        }
        return true;
    }
}

continue ở trường hợp cả hai null là có chủ ý. Các cặp null-null là ranh giới lá hợp lệ — bạn enqueue chúng (vì bạn luôn đẩy cả hai con), rồi bỏ qua khi dequeue. Một cách thay thế là guard việc enqueue bằng null check, nhưng điều đó làm điều kiện khó đọc hơn.

Trace Example 1: p = [1,2,3], q = [1,2,3]

Ban đầu:  queue = [(1,1)]

Dequeue (1,1): cả hai không null, giá trị khớp (1==1)
  -> enqueue (2,2), (3,3)
  queue = [(2,2), (3,3)]

Dequeue (2,2): cả hai không null, giá trị khớp (2==2)
  -> enqueue (null,null), (null,null)
  queue = [(3,3), (null,null), (null,null)]

Dequeue (3,3): cả hai không null, giá trị khớp (3==3)
  -> enqueue (null,null), (null,null)
  queue = [(null,null), (null,null), (null,null), (null,null)]

Dequeue (null,null): cả hai null -> continue
Dequeue (null,null): cả hai null -> continue
Dequeue (null,null): cả hai null -> continue
Dequeue (null,null): cả hai null -> continue

queue rỗng -> return true

Mỗi node được thăm đúng một lần. Các cặp null tốn mỗi lần một dequeue và một continue — chúng thêm O(n) work tổng cộng, nhưng không thay đổi giới hạn tiệm cận.

Time và space complexity

Time: O(min(m, n)), cùng lý luận với DFS. Bạn xử lý từng cặp cho đến khi phân kỳ hoặc hết node.

Space: O(min(m, n)) cho queue. Ở level rộng nhất của cây cân bằng, queue chứa khoảng n/2 cặp. Với chuỗi lệch, queue không bao giờ chứa nhiều hơn một cặp tại một thời điểm. Trong trường hợp xấu nhất cho BFS (cây cân bằng hoàn hảo), space là O(n). Trong trường hợp xấu nhất cho DFS (chuỗi lệch), space cũng là O(n). Hằng số khác nhau, nhưng O class giống nhau.

Các edge case, được phân tích cụ thể

Cả hai cây null (p = null, q = null): trong DFS, base case đầu tiên kích hoạt ngay và trả về true. Trong BFS, enqueue ban đầu đặt (null, null) vào queue, dequeue nhấn điều kiện cả-hai-null, và continue làm queue trống; vòng while kết thúc và trả về true. Cả hai đúng.

Một cây null (p = [1], q = null): DFS nhấn base case hai — một không null, một null — và trả về false. BFS dequeue (node_1, null), nhấn nhánh đơn-null, trả về false. Một lần gọi trong cả hai trường hợp.

Hai cây cấu trúc khác nhau, giá trị giống nhau: p = [1,2], q = [1,null,2] là Example 2. Cả hai cây đều có node giá trị 1 và 2, nhưng node 2 là con trái trong p và con phải trong q. Kiểm tra giá trị qua ở root. Tại subtree trái, p.left = 2 và q.left = null phân kỳ ngay. Thuật toán không cần nhìn q.right để biết câu trả lời.

Cây chỉ có một node: p = [5], q = [5]. DFS recurse vào isSameTree(null, null) hai lần và nhấn base case một cả hai lần. Trả về true. Không có gì bất ngờ.

Giá trị âm và số 0: p.val = -10⁴ và q.val = 0 sẽ so sánh đúng là không bằng nhau. Phép so sánh là trực tiếp; không cần xử lý đặc biệt cho dải giá trị.

Nên viết approach nào, và khi nào

Tôi chọn phiên bản DFS ngay lập tức. Cấu trúc đệ quy khớp với định nghĩa đệ quy của bài toán: hai cây giống nhau nếu root của chúng khớp và các subtree của chúng giống nhau. Code gần như là bản dịch trực tiếp của định nghĩa đó. Ai đọc cũng có thể kiểm tra trong mười giây.

Phiên bản BFS đáng biết, nhưng không phải vì nó nhanh hơn hay dùng ít bộ nhớ hơn — không phải vậy. Lý do biết nó là đôi khi bạn cần xử lý hai cây theo từng level, và việc xây dựng pattern "shared queue với các cặp node" trong đầu rất hữu ích cho những bài mà BFS thực sự cần thiết (so sánh level-order, chẳng hạn). Same Tree là nơi tốt để thấy kỹ thuật này trong một tình huống đơn giản.

Lý luận stack overflow — thường được viện dẫn để chọn BFS — không áp dụng ở đây. 100 node, tối đa 100 stack frame. Lo ngại đó là thực với n = 10⁵, không phải n = 100.

Bảng so sánh

Độ phức tạp giống hệt nhau. Đây không phải câu hỏi "cái nào nhanh hơn". Là câu hỏi "cái nào rõ ràng hơn", và phiên bản đệ quy thắng với bài toán này.

Vị trí trong series trees

Đây là bài thứ tư trong series, sau Maximum Depth of Binary Tree (104), Invert Binary Tree (226), và Binary Tree Level Order Traversal (102). Ba bài kia đã thiết lập các pattern duyệt cây chính — DFS recursion trên một cây, BFS với queue. Same Tree là bài đầu tiên trong series nhận hai cây làm input. Đó là bước khái niệm: thay vì hỏi "điều gì đúng về cây này", bạn hỏi "mối quan hệ giữa hai cây này là gì."

Ba base case ở đây — cả hai null, một null, giá trị khác — xuất hiện liên tục trong những bài so sánh hoặc kết hợp cây. Nhận ra pattern đó mới là kỹ năng có thể chuyển giao.

Symmetric Tree (101) là câu hỏi tiếp theo tự nhiên: thay vì so sánh hai cây riêng biệt, kiểm tra xem một cây có phải là mirror của chính nó không. Recursion thay đổi từ isSameTree(p.left, q.left) and isSameTree(p.right, q.right) sang so sánh left.left với right.right và left.right với right.left — cùng cấu trúc so sánh, nhưng theo chiều chéo.

Subtree of Another Tree (572) mở rộng Same Tree trực tiếp. Bạn kiểm tra xem có subtree nào của root giống hệt subRoot không. Implementation gọi một helper về cơ bản là isSameTree tại mỗi root ứng cử viên. Nếu bài này cảm thấy thoải mái, 572 là bước leo thang tự nhiên.

Flip Equivalent Binary Trees (951) nới lỏng phép so sánh: hai cây flip-equivalent nếu bạn có thể làm chúng giống nhau bằng cách hoán đổi một số con. Các base case giống nhau; trường hợp đệ quy thêm một or — kiểm tra cùng thứ tự và kiểm tra thứ tự hoán đổi. Một instance khác của pattern "so sánh các cặp node tương ứng" với điều kiện thành công được sửa đổi.

Merge Two Binary Trees (617) là phần bù construction. Thay vì so sánh hai cây, bạn xây dựng cây mới bằng cách cộng các giá trị tương ứng. Cấu trúc duyệt cây giống hệt; chỉ phép toán tại mỗi node thay đổi.