Bài toán
Cho hai cây root và subRoot. Kiểm tra xem subRoot có phải là một cây con (subtree) nằm trong root hay không.
Một cây con bao gồm một node và tất cả các hậu duệ của nó.
Phân Tích & Tiếp Cận
Đệ quy kết hợp
Một cây subRoot là cây con của root nếu:
subRootgiống hệtroot(dùng hàmisSameTreebài trước để check).- HOẶC
subRootlà cây con củaroot.left. - HOẶC
subRootlà cây con củaroot.right.
typescript:
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
if (!subRoot) return true; // Cây rỗng luôn là subtree
if (!root) return false; // Cây gốc rỗng thì không chứa ai cả
// Kiểm tra xem giống hệt ngay tại đây không
if (isSameTree(root, subRoot)) return true;
// Nếu không, tìm thử ở con trái hoặc con phải
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
// Hàm bổ trợ từ bài trước
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}- Time Complexity: $O(n \cdot m)$ - Với mỗi node của cây gốc (n), ta có thể phải duyệt hết cây con (m) để so sánh.
- Space Complexity: $O(h)$.