Same Tree

Bài toán

Cho p và q là root của hai cây nhị phân. Kiểm tra xem chúng có giống hệt nhau không (cấu trúc giống nhau và giá trị giống nhau).

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

Đệ quy (DFS)

Hai cây A và B giống nhau KHI VÀ CHỈ KHI:

1. Root của A và B cùng null (giống nhau ở chỗ cùng rỗng).
2. Hoặc:
   • Root của A và B đều KHÔNG null.
   • Giá trị A.val === B.val.
   • Cây con trái của A giống cây con trái của B (isSameTree(A.left, B.left)).
   • Cây con phải của A giống cây con phải của B (isSameTree(A.right, B.right)).

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    // Base Case 1: Cả hai đều null -> Giống nhau
    if (!p && !q) return true;
    
    // Base Case 2: Một trong hai null, hoặc giá trị khác nhau -> Khác nhau
    if (!p || !q || p.val !== q.val) return false;

    // Recursive Step
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

• Time Complexity: $O(n)$.
• Space Complexity: $O(h)$.