Subtree of Another Tree: khi Same Tree trở thành bài toán con

Same Tree (bài 100) hỏi hai cây có giống nhau không. Bài này hỏi liệu một cây có xuất hiện dưới dạng subtree có gốc, liên thông bên trong một cây khác không — thực chất là gọi Same Tree lặp đi lặp lại, một lần cho mỗi node của cây ngoài. Mối quan hệ giữa hai bài không chỉ là gợi ý học thuật; hàm isIdentical bạn viết ở đây là hàm isSameTree từ bài trước, dùng nguyên không chỉnh sửa.

Câu hỏi mang tính cấu trúc: có node nào trong root bắt đầu một subtree giống hệt — cùng hình dạng, cùng giá trị, đến tận các lá — với subRoot không? Lưu ý "liên thông" đã được baked vào định nghĩa. Bạn không thể chọn bất kỳ node nào từ các tầng khác nhau. Một subtree là một node và tất cả các node con của nó.

Ràng buộc nói lên điều gì

root có tối đa 2000 node. subRoot tối đa 1000 node. Giá trị nằm trong [-10⁴, 10⁴].

Kích thước này khá nhỏ. 2000 node cho root nghĩa là độ sâu đệ quy worst-case là 2000 (chuỗi lệch hoàn toàn). Recursion limit mặc định của Python là 1000 lần gọi, nên về lý thuyết trên chuỗi lệch tối đa bạn có thể gặp lỗi — nhưng trong thực tế, judge của LeetCode không enforce giới hạn 1000 level nghiêm ngặt với cây kích thước này. Nếu gặp lỗi, tăng sys.setrecursionlimit lên một chút là xong; không cần đổi sang iteration trừ khi đề yêu cầu.

Điểm mấu chốt là tương tác giữa hai kích thước: nếu root có m node và subRoot có n node, brute-force tốn O(m × n). Với m = 2000 và n = 1000, đó là 2 × 10⁶ phép so sánh node — hoàn toàn trong ngưỡng một giây. Ràng buộc không đòi hỏi bạn phải dùng approach serialization; nó chỉ khiến approach đó khả thi như một tối ưu hóa nếu muốn.

Dải giá trị [-10⁴, 10⁴] quan trọng với serialization. Khi chuyển cây thành string, bạn cần phân biệt số 1 theo sau số 2 (hai node riêng biệt) với số 12 (một node). Đó là cái bẫy trong approach 2.

Approach 1: DFS với helper same-tree

Duyệt mọi node của root. Tại mỗi node, kiểm tra xem subtree có gốc tại đó có giống hệt subRoot không. Nếu có, trả về true. Nếu không, tiếp tục xuống con trái và con phải.

Hai hàm: isSubtree thực hiện duyệt; isIdentical thực hiện so sánh tại một cặp gốc.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        if self.isIdentical(root, subRoot):
            return True
        return (self.isSubtree(root.left, subRoot) or
                self.isSubtree(root.right, subRoot))
 
    def isIdentical(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        return (s.val == t.val and
                self.isIdentical(s.left, t.left) and
                self.isIdentical(s.right, t.right))

public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (IsIdentical(root, subRoot)) return true;
        return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
    }
 
    private bool IsIdentical(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val
            && IsIdentical(s.left, t.left)
            && IsIdentical(s.right, t.right);
    }
}

Trace tay qua Example 1

root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2], kết quả mong đợi: true.

Bắt đầu từ node 3. isIdentical(node-3, node-4): vals khác (3 ≠ 4) -> false. Chuyển sang con trái của root là node 4. isIdentical(node-4, node-4): vals khớp. Đệ quy sang trái: isIdentical(node-1, node-1) -> vals khớp, cả hai con đều null -> true. Đệ quy sang phải: isIdentical(node-2, node-2) -> vals khớp, cả hai con đều null -> true. Vậy isIdentical tại node 4 trả về true. isSubtree trả về true ngay; subtree bên phải (node 5) không bao giờ được thăm.

Example 2 thêm node 0 bên dưới node 2 trong root. Khi đến node 4 của root lần này, isIdentical đệ quy đến node 2 bên trái rồi bên phải. Trên cây trái, so sánh đến con trái của node 2 (là node 0) với con trái của node 2 trong subRoot (là null). Một bên non-null, một bên null -> false. isIdentical trả về false. isSubtree tiếp tục đến node 5 của root, thử isIdentical(node-5, node-4), thất bại ngay. Trả về false.

Độ phức tạp

• Time: O(m × n) — với mỗi trong m node của root, ta có thể chạy isIdentical, duyệt đến n node của subRoot.
• Space: O(max(H_root, H_sub)) — độ sâu call stack bị giới hạn bởi cây cao hơn. Worst case O(m + n) với hai chuỗi lệch hoàn toàn.

Approach 2: String serialization với delimiter an toàn

Serialize cả hai cây thành string bằng preorder traversal, sau đó kiểm tra xem string của subRoot có xuất hiện như một substring của string root không. Nếu có, match cấu trúc tồn tại.

Nghe đơn giản. Cái bẫy nằm ở thiết kế delimiter. Giả sử bạn serialize một node có giá trị 1 thành "1" và null thành "". String của cây đơn node có giá trị 12 và string của hai node liên tiếp có giá trị 1 và 2 có thể trùng nhau. Bạn cần delimiter đủ mạnh để các giá trị không nhập nhằng.

Giải pháp: prefix mỗi giá trị bằng ký tự tách không thể xuất hiện trong số nguyên, và đặt cho null một token riêng biệt. Ở đây dùng # trước mỗi giá trị thực và #null cho node null.

serialize([4,1,2])      = "#4#1#null#null#2#null#null"
serialize([3,4,5,1,2])  = "#3#4#1#null#null#2#null#null#5#null#null"

Substring "#4#1#null#null#2#null#null" xuất hiện đúng một lần trong string thứ hai, tại vị trí 2. Không có false positive vì # trước giá trị đảm bảo giá trị bắt đầu tại đó, không phải ở giữa chữ số.

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#null"
            return f"#{node.val}{serialize(node.left)}{serialize(node.right)}"
 
        return serialize(subRoot) in serialize(root)

public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        return Serialize(root).Contains(Serialize(subRoot));
    }
 
    private string Serialize(TreeNode node) {
        if (node == null) return "#null";
        return $"#{node.val}{Serialize(node.left)}{Serialize(node.right)}";
    }
}

Hàm string.Contains trong C# dùng naive substring search nội bộ (không đảm bảo KMP). Với string độ dài O(m) và O(n), average case vẫn đủ nhanh. Nếu cần đảm bảo O(m + n) tuyệt đối, triển khai KMP hoặc Rabin-Karp trên các string đã serialize — nhưng với ràng buộc m ≤ 2000 này, Contains là ổn.

Độ phức tạp

• Time: O(m + n) — mỗi cây serialize một lần, sau đó substring search trên string tổng độ dài tỷ lệ với m + n.
• Space: O(m + n) — hai string đã serialize. Call stack đệ quy là O(H_root + H_sub), bị chi phối bởi phần lưu string.

Edge cases

subRoot chính là root. isIdentical(root, subRoot) là kiểm tra đầu tiên trong isSubtree. Nếu hai cây giống nhau, trả về true ở lần gọi đầu. Trong serialization, serialize(subRoot) == serialize(root), nên in trả về true. Cả hai approach đều xử lý đúng.

subRoot lớn hơn root (nhiều node hơn). isSubtree đệ quy cho đến khi root là null, rồi trả về false. Trong serialization, một string dài hơn không thể là substring của string ngắn hơn — toán tử in của Python trả về false ngay lập tức nếu len(needle) > len(haystack).

Các giá trị có tiền tố chữ số giống nhau, ví dụ 1 và 12. Approach 1 so sánh giá trị integer, nên 1 != 12 là hiển nhiên. Approach 2 không có prefix # sẽ serialize [1, 12] và một node có giá trị 112 giống hệt nhau. Với prefix # thì thành #1#12 vs #112 — rõ ràng không nhầm.

subRoot là null. Ràng buộc đề đảm bảo subRoot có ít nhất một node (dải [1, 1000]), nên trường hợp này không xảy ra. Nếu có thể, câu trả lời chuẩn là true — null là subtree hợp lệ (rỗng) của bất kỳ cây nào.

Cả hai cây là một node đơn với giá trị giống nhau. isIdentical trả về true tại gốc; isSubtree short-circuit ở lần gọi đầu.

So sánh hai approach

Với ràng buộc đề — m ≤ 2000, n ≤ 1000 — tôi sẽ ship approach 1 trong phỏng vấn mà không cần xin lỗi. Phép tính ra: 2 × 10⁶ operation, không cấp phát string, không có gì có thể sai trong thiết kế delimiter. Approach 2 là câu trả lời đúng nếu ai đó đặt bài toán này với m và n trong hàng triệu, hoặc nếu kiểm tra same-tree tốn kém (chẳng hạn node chứa số thực với so sánh theo dung sai). Ở 2000 node, overhead xây dựng và tìm kiếm string thực tế có thể chậm hơn DFS — heap allocation và substring search có constant thực không nhỏ.

Nhưng approach 2 thực sự elegant và đáng biết. Insight ở đây — "biến câu hỏi cấu trúc thành câu hỏi string, rồi dùng string search nhanh" — xuất hiện lại trong các bài như Serialize and Deserialize Binary Tree (297) và Find Duplicate Subtrees (652).

Vị trí trong series và các bài liên quan

Đây là bài thứ năm trong series trees. Hành trình đến đây:

• Bài 104 và 226 giới thiệu DFS trên một cây: tính một tính chất của toàn bộ cây bằng recursion.
• Bài 102 giới thiệu BFS theo level-order: xử lý node theo từng tầng với queue.
• Bài 100 giới thiệu DFS trên hai cây: so sánh hai cây node theo node. Hàm isIdentical đó chính là core của bài này.
• Bài 572 (bài này) kết hợp so sánh hai cây vào một cuộc tìm kiếm: gọi isIdentical tại mỗi node của cây ngoài.

Pattern kết hợp — dùng bài toán con đã giải như một subroutine bên trong một traversal — xuất hiện ở nhiều bài liên quan:

652. Find Duplicate Subtrees. Với mỗi node, xác định xem cấu trúc subtree của nó có xuất hiện ở nơi nào khác trong cùng cây không. Approach serialization từ đây ánh xạ trực tiếp: serialize mọi subtree, dùng hash map để phát hiện trùng lặp. Cùng kỹ thuật, câu hỏi khác.

1367. Linked List in Binary Tree. Cho một linked list và một cây nhị phân, kiểm tra xem list có xuất hiện như một đường đi đi xuống trong cây không. Cùng cấu trúc traversal ngoài (thăm mọi node), kiểm tra trong khác (match tiền tố list từ node đó). Giống hệt 572 về cấu trúc nhưng kiểm tra trong là list walk thay vì so sánh cây.

124. Binary Tree Maximum Path Sum. Không phải bài subtree matching, nhưng thể hiện cùng pattern "tại mỗi node, tính gì đó phụ thuộc vào cả hai subtree và quyết định có cập nhật kết quả toàn cục không." Traversal ngoài điều khiển kết quả toàn cục; logic trong là đóng góp của mỗi node.

297. Serialize and Deserialize Binary Tree. Approach serialization trong bài này là phiên bản đơn giản hóa của serialization cây đầy đủ. Bài 297 yêu cầu encoding và decoding roundtrip đúng với cây tùy ý — cùng ý tưởng preorder-với-null-markers, yêu cầu correctness khắt khe hơn.