1.1 Recursion là gì?

Hai thành phần bắt buộc

1. Base case — điều kiện dừng. Ví dụ: n == 0, node is None.
2. Recursive case — quy về bài nhỏ hơn. Ví dụ: fib(n-1) + fib(n-2).

Nếu thiếu base case → vô tận, stack overflow. Nếu recursive case không thực sự nhỏ hơn → cũng vô tận.

Ví dụ kinh điển

def factorial(n):
    if n <= 1: return 1            # base case
    return n * factorial(n - 1)    # recursive case — gọi với n nhỏ hơn

Hai dòng — toàn bộ định nghĩa giai thừa.

1.2 Cách suy nghĩ đúng — "Leap of Faith"

Đa số sinh viên thất bại với đệ quy vì cố theo dấu mọi lời gọi trong đầu. Đó là sai lầm.

Ví dụ — Tổng node trong cây

def total(root):
    if not root: return 0                          # base
    return root.val + total(root.left) + total(root.right)
    # Tin rằng total(root.left) trả tổng cây con trái — không cần lo cách nó tính

Đừng cố hình dung "total đi đến đâu rồi quay lại". Hãy nghĩ: "Nếu hai cây con có tổng đúng, tổng cả cây = root + tổng trái + tổng phải".

Đây là kỹ năng quan trọng nhất của tuần. Khi nắm được, mọi bài tree trở nên dễ.

1.3 Recursion vs Iteration

Khi nào ưu tiên cái nào?

• Recursion: cây, đồ thị, divide & conquer, backtracking — đệ quy là ngôn ngữ tự nhiên.
• Iteration: array, sliding window, pattern tuần tự — đơn giản và an toàn về stack.

Trong phỏng vấn, nếu được hỏi cả hai cách (như Reverse Linked List ở Tuần 5), nên biết để đáp ứng.

1.4 Bốn bẫy đệ quy thường gặp

1. Quên / sai base case. Chương trình chạy mãi → RecursionError. Luôn xử lý None, mảng rỗng, n = 0/1.
2. Lời gọi không "nhỏ hơn".

   # SAI — n không nhỏ đi
   def f(n):
       if n == 0: return 0
       return f(n) + 1   # vô tận!

3. Đệ quy ngây thơ với lời gọi lặp. Fibonacci kiểu O(2ⁿ) → cực chậm. Cần memoisation (Tuần 12).
4. Mutate biến shared.

   # Bài Path Sum II — backtracking với list
   def dfs(node, path):
       path.append(node.val)
       ...
       # QUÊN path.pop() ở cuối → các nhánh sau bị "ô nhiễm"

   Sẽ đào sâu ở Tuần 11 (Backtracking).

Python mặc định giới hạn đệ quy ~1000. Tăng bằng sys.setrecursionlimit(10000) nếu cần.

2.1 TreeNode trong Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Các loại tree quan trọng

• Binary Tree: mỗi node có ≤ 2 con. Không ràng buộc thêm.
• Binary Search Tree (BST): với mọi node, tất cả giá trị bên trái < root.val, bên phải > root.val.
• Balanced Tree: chiều cao trái và phải khác nhau ≤ 1 với mọi node. Đảm bảo O(log n) operations.
• Complete Tree: mọi level đầy, trừ level cuối lấp từ trái.
• Full Tree: mỗi node có đúng 0 hoặc 2 con.

2.2 Ba phép duyệt — Trực quan

Tính chất quan trọng: Inorder của BST cho ra sequence sort tăng dần — dùng để verify BST hoặc tìm phần tử thứ k nhỏ nhất.

2.3 Code ba phép duyệt

Recursive — gọn nhất

def preorder(root):
    if not root: return
    print(root.val)         # xử lý ROOT
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if not root: return
    inorder(root.left)
    print(root.val)         # xử lý ROOT giữa
    inorder(root.right)

def postorder(root):
    if not root: return
    postorder(root.left)
    postorder(root.right)
    print(root.val)         # xử lý ROOT cuối

Iterative Inorder — dùng stack (kinh điển)

def inorder(root):
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)        # đi sâu nhất bên trái
            cur = cur.left
        cur = stack.pop()
        print(cur.val)
        cur = cur.right

Time O(n) cho mọi phép duyệt; Space O(h) với h = chiều cao.

2.4 Level-order Traversal — BFS với Queue

Thay vì DFS, đôi khi cần duyệt theo từng tầng (level). Dùng deque như queue:

from collections import deque
def levelOrder(root):
    if not root: return []
    res = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):                # snapshot kích thước hiện tại
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

Áp dụng: Right Side View, Zigzag Traversal, Average of Levels, Connect Next Right Pointers.

3.1 Top-down vs Bottom-up DFS

Top-down — mẫu

def helper(node, accumulated_info):
    if not node: return
    new_info = combine(accumulated_info, node.val)
    helper(node.left, new_info)
    helper(node.right, new_info)

Bottom-up — mẫu

def helper(node):
    if not node: return base_value
    left_info = helper(node.left)
    right_info = helper(node.right)
    return combine(node.val, left_info, right_info)

3.2 Worked Example 1 — Maximum Depth (Bottom-up)

Đề (LeetCode #104): Cho root của cây nhị phân. Tìm chiều sâu lớn nhất (số node trên đường dài nhất từ root đến leaf).

def maxDepth(root):
    if not root: return 0                  # base — cây rỗng có chiều sâu 0
    left = maxDepth(root.left)             # tin: trả đúng chiều sâu cây con trái
    right = maxDepth(root.right)
    return 1 + max(left, right)            # 1 (cho root hiện tại) + chiều sâu lớn hơn của 2 con

Trace với cây ở slide 2.2

• maxDepth(4) = 1 + max(0, 0) = 1
• maxDepth(5) = 1 + max(0, 0) = 1
• maxDepth(6) = 1 + max(0, 0) = 1
• maxDepth(2) = 1 + max(1, 1) = 2
• maxDepth(3) = 1 + max(0, 1) = 2
• maxDepth(1) = 1 + max(2, 2) = 3 ✓

Time O(n), Space O(h).

3.3 Worked Example 2 — Same Tree (Top-down)

Đề (LeetCode #100): Cho hai cây p, q. Trả True nếu cấu trúc và giá trị giống nhau.

def isSameTree(p, q):
    if not p and not q: return True             # cả hai rỗng → đúng
    if not p or not q: return False             # một rỗng → sai
    if p.val != q.val: return False             # giá trị khác → sai
    return (isSameTree(p.left, q.left)
            and isSameTree(p.right, q.right))

Time O(n) với n = số node của cây nhỏ hơn (dừng sớm khi khác); Space O(h).

Cách viết khác — gộp base case

def isSameTree(p, q):
    if not p or not q: return p is q            # hai cùng None → True; một None → False
    return p.val == q.val and \
           isSameTree(p.left, q.left) and \
           isSameTree(p.right, q.right)

3.4 Worked Example 3 — Symmetric Tree

Đề (LeetCode #101): Trả True nếu cây đối xứng qua trục giữa.

Quan sát

Cây đối xứng ⟺ cây con trái và cây con phải là phản chiếu của nhau:

• Trái của trái = Phải của phải.
• Phải của trái = Trái của phải.

def isSymmetric(root):
    def mirror(a, b):
        if not a and not b: return True
        if not a or not b: return False
        return (a.val == b.val
                and mirror(a.left, b.right)
                and mirror(a.right, b.left))
    return mirror(root.left, root.right) if root else True

Cùng tinh thần Same Tree, nhưng so sánh chéo thay vì cùng phía.

Time O(n), Space O(h).

3.5 Worked Example 4 — Invert Binary Tree

Đề (LeetCode #226): Đổi left và right tại mọi node.

def invertTree(root):
    if not root: return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Time O(n), Space O(h).

Phân tích — Tinh thần "leap of faith" tột bậc

Một dòng để invert. Tại sao đúng?

• invertTree(root.left) trả về cây con trái đã được đảo.
• invertTree(root.right) trả về cây con phải đã được đảo.
• Gán chéo → cây hiện tại được đảo.

Knowledge Check — DFS Patterns

4.1 Pattern: Đệ quy trả về thông tin tổng hợp

Khi nào áp dụng?

• Cần biết "chiều sâu cây con" + cập nhật "đường dài nhất qua tổng cây".
• Cần biết "max gain qua node" + cập nhật "max path sum".
• Cần verify thuộc tính (BST) + truyền biên (min, max) qua các con.

Pattern này xuất hiện ở: Diameter, Max Path Sum, Validate BST, House Robber III. Đây là pattern đặc trưng của bài tree Medium/Hard.

4.2 Worked Example 5 — Diameter of Binary Tree

Đề (LeetCode #543): Diameter = số cạnh trên đường dài nhất giữa hai node bất kỳ. Đường có thể không đi qua root.

Quan sát then chốt

Đường dài nhất qua node X có cấu trúc: nhánh trái sâu nhất + node X + nhánh phải sâu nhất = depth(X.left) + depth(X.right).

Đáp án = max của tổng này qua mọi node.

def diameterOfBinaryTree(root):
    diameter = 0
    def depth(node):
        nonlocal diameter
        if not node: return 0
        left = depth(node.left)
        right = depth(node.right)
        diameter = max(diameter, left + right)        # cập nhật ans
        return 1 + max(left, right)                   # trả depth lên cha
    depth(root)
    return diameter

Time O(n), Space O(h).

4.3 Diameter — Vì sao "split" tại node?

Bài này minh hoạ rõ pattern "thông tin trả lên ≠ ans":

• depth(node) trả về chiều sâu — để cha dùng.
• diameter được cập nhật như side effect — đáp án thực sự.

Vì sao không thể trả "diameter" và truyền lên?

Vì cha không thể "ghép" diameter của con trái với diameter của con phải để ra diameter của cha. Hai diameter của con có thể là đường không đi qua node hiện tại.

Cha chỉ cần biết "nhánh sâu nhất xuyên qua mỗi con" để tính đường mới qua chính cha.

4.4 Worked Example 6 — Path Sum I & II

Đề Path Sum (LeetCode #112): Trả True nếu có đường từ root đến leaf có tổng = target.

def hasPathSum(root, target):
    if not root: return False
    if not root.left and not root.right:           # leaf
        return root.val == target
    remain = target - root.val
    return (hasPathSum(root.left, remain)
            or hasPathSum(root.right, remain))

Top-down — truyền remain xuống.

Path Sum II (#113) — liệt kê mọi đường

def pathSum(root, target):
    res = []
    def dfs(node, remain, path):
        if not node: return
        path.append(node.val)
        if not node.left and not node.right and remain == node.val:
            res.append(path[:])                    # COPY path!
        dfs(node.left, remain - node.val, path)
        dfs(node.right, remain - node.val, path)
        path.pop()                                 # backtrack
    dfs(root, target, [])
    return res

Time O(n²) worst (mỗi đường có thể dài O(n), copy O(n)). Bẫy: quên path.pop() hoặc quên path[:] để copy. Sẽ học sâu ở Tuần 11.

4.5 Worked Example 7 — Lowest Common Ancestor

Đề (LeetCode #236): Cho cây và hai node p, q. Tìm tổ tiên chung thấp nhất.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root                 # p và q ở hai phía
    return left if left else right                 # cả hai ở một phía

Time O(n), Space O(h).

Phân tích 4 case

1. Cả p và q ở cây con trái → left ≠ None, right = None → trả left.
2. Cả p và q ở cây con phải → tương tự → trả right.
3. Một ở trái, một ở phải → cả left và right ≠ None → root chính là LCA.
4. Root chính là p hoặc q → base case trả ngay.

4.6 LCA — Tinh thần và bẫy

Vì sao base case root == p or root == q đủ?

Khi gặp p (hoặc q), trả về luôn — không cần tiếp tục đi sâu. Vì:

• Nếu q là hậu duệ của p → p chính là LCA. Trả p, hàm cha không tìm thấy q ở nhánh khác → trả p lên.
• Nếu q không phải hậu duệ → ở nhánh khác. Hàm cha sẽ nhận left = p, right = q (hoặc ngược) → trả root cha.

Đề bảo đảm p và q tồn tại — đó là điều kiện then chốt cho trick này hoạt động.

Biến thể BST — đơn giản hơn

def lowestCommonAncestorBST(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root        # phân kỳ → root là LCA

Tận dụng tính chất BST: O(h) thay vì O(n). h = log n nếu cây balanced.

4.7 Worked Example 8 — Validate Binary Search Tree

Đề (LeetCode #98): Cho root. Trả True nếu cây là BST hợp lệ.

Bẫy phổ biến

# SAI — chỉ check con trực tiếp, không check toàn cây con
def isValidBST_WRONG(root):
    if not root: return True
    if root.left and root.left.val >= root.val: return False
    if root.right and root.right.val <= root.val: return False
    return isValidBST_WRONG(root.left) and isValidBST_WRONG(root.right)
# Sai trên cây [5, 1, 4, null, null, 3, 6] — node 3 nhỏ hơn 5 nhưng nằm bên phải

Đúng — truyền biên (min, max)

def isValidBST(root):
    def valid(node, low, high):
        if not node: return True
        if node.val <= low or node.val >= high:
            return False
        return (valid(node.left, low, node.val)
                and valid(node.right, node.val, high))
    return valid(root, float('-inf'), float('inf'))

Top-down: truyền biên xuống. Mỗi khi đi trái, biên trên = root.val; đi phải, biên dưới = root.val.

Cách 2 — In-order check

Inorder của BST sort tăng → kiểm tra "phần tử trước < phần tử hiện tại" qua từng bước inorder.

Knowledge Check — Information Aggregation

5.1 Pattern Divide & Conquer

Master Theorem (sơ lược)

Với T(n) = a·T(n/b) + O(n^c):

• Nếu c > log_b(a): T(n) = O(n^c).
• Nếu c = log_b(a): T(n) = O(n^c · log n).
• Nếu c < log_b(a): T(n) = O(n^(log_b a)).

Ví dụ Merge Sort: T(n) = 2·T(n/2) + O(n) → a=2, b=2, c=1, log₂(2) = 1 → case giữa → O(n log n).

Sinh viên không cần học thuộc Master Theorem — chỉ cần hiểu để giải thích tại sao Merge Sort là O(n log n).

5.2 Worked Example 9 — Merge Sort

def mergeSort(arr):
    if len(arr) <= 1: return arr               # base
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])                # divide + conquer
    right = mergeSort(arr[mid:])
    return merge(left, right)                  # combine

def merge(a, b):
    res = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:]); res.extend(b[j:])
    return res

Time O(n log n), Space O(n).

Tính chất

• Stable: phần tử bằng nhau giữ thứ tự gốc.
• Worst case = Average = Best: luôn O(n log n) — không phụ thuộc input.
• Tốn O(n) bộ nhớ phụ — bất lợi so với Quick Sort.

Đây là thuật toán sorted trong Python (Timsort = Merge Sort cải tiến).

5.3 Worked Example 10 — Quick Sort

def quickSort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quickSort(arr, lo, p - 1)
        quickSort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

Tính chất

• Time: O(n log n) trung bình; O(n²) worst case (mảng đã sort, pivot kém).
• In-place: O(log n) space cho call stack.
• Không stable.

Mở rộng: Quick Select — tìm phần tử thứ k trong O(n) trung bình

Áp dụng partition + đệ quy 1 phía. Là pattern quan trọng cho Top K Frequent (Tuần 9 — Heap có cách khác).

Knowledge Check — D&C

6.0 Decision Tree — Bài Tree

Quy trình code bài tree

1. Vẽ cây mẫu trên giấy.
2. Tự hỏi: "Đệ quy con cần trả gì để giải bài hiện tại?"
3. Viết base case (None → ?).
4. Viết recursive case dựa trên "leap of faith".

Tổng kết Tuần 8

Đã học

• Recursion mindset: leap of faith — tin lời gọi con đúng, ráp lại tại node hiện tại.
• Tree basics: TreeNode, ba phép duyệt (preorder, inorder, postorder), tính chất inorder của BST.
• Level-order BFS với mẹo for _ in range(len(q)).
• Top-down vs Bottom-up DFS: hai cách tư duy đệ quy.
• Information Aggregation Pattern: trả về thông tin truyền lên ≠ ans, cập nhật ans như side effect.
• Bài tree kinh điển: Maximum Depth, Diameter, Path Sum, LCA, Validate BST, Same/Symmetric/Invert Tree.
• Divide & Conquer: Merge Sort O(n log n) đảm bảo, Quick Sort average O(n log n) in-place.

Bài về nhà (12 bài)

1. LeetCode #104 — Maximum Depth of Binary Tree
2. LeetCode #100 — Same Tree
3. LeetCode #101 — Symmetric Tree
4. LeetCode #226 — Invert Binary Tree
5. LeetCode #543 — Diameter of Binary Tree
6. LeetCode #112 — Path Sum & #113 Path Sum II
7. LeetCode #236 — Lowest Common Ancestor of Binary Tree
8. LeetCode #235 — LCA of BST (variant)
9. LeetCode #98 — Validate Binary Search Tree
10. LeetCode #102 — Binary Tree Level Order Traversal
11. LeetCode #199 — Binary Tree Right Side View
12. LeetCode #124 — Binary Tree Maximum Path Sum (Hard)