Chương 11 - Depth-First Search (DFS)

DFS đi sâu nhất có thể trước khi quay lui. Đây là pattern tự nhiên cho mọi bài cây / đồ thị có cấu trúc đệ quy: depth, path sum, validate, LCA, … Chương này tập trung DFS trên cây - pattern dễ thuộc lòng và rất hay trong phỏng vấn. DFS trên grid sẽ ở Chương 12 (Island Matrix).

Mục tiêu chương

Sau chương này, bạn sẽ:

Phân biệt preorder / inorder / postorder và khi dùng.
Thuộc 3 mẫu: top-down, bottom-up, hỗn hợp.
Hiểu BST validation cần bound, không chỉ check child.
Gateway sang Tree DP (Ch 42) và Backtracking (Ch 28).

Khi nào dùng pattern này?

Cây / DAG / graph cần duyệt theo độ sâu.
Tính giá trị bottom-up (giá trị node phụ thuộc các con).
Tìm path từ root đến lá thoả điều kiện.
Khi không cần đường đi ngắn nhất - chỉ cần có/không/đếm/liệt kê.

3 mẫu DFS trên cây: 1. Top-down: truyền state xuống (vd. path_so_far, current_sum). 2. Bottom-up: leaf trả giá trị lên, node tổng hợp từ con. 3. Hỗn hợp: vừa truyền xuống vừa nhận lên.

Định dạng input (áp dụng cho TẤT CẢ bài tree trong chương)

Mọi bài trong chương 10/11/22 (tree) dùng TreeNode chuẩn của LeetCode:

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

Tham số root luôn là một node TreeNode (hoặc None nếu cây rỗng).
Khi ví dụ ghi Input: root = [1, 2, 3, null, 4], đây là LC level-order serialize - đọc theo BFS, null là vị trí thiếu con. Cây thực tế: 1 là root, 2/3 là con trái/phải; 2.left = None, 2.right = TreeNode(4).
Output: thường trả về root/int/list[list[int]] tùy bài.

Template code

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


# 1) Bottom-up: trả về giá trị từ con
def dfs_bottom_up(node) -> int:
    if not node:
        return 0
    left = dfs_bottom_up(node.left)
    right = dfs_bottom_up(node.right)
    return combine(node.val, left, right)


# 2) Top-down: truyền state xuống
def dfs_top_down(node, state) -> None:
    if not node:
        return
    new_state = update(state, node.val)
    if is_leaf(node):
        # ... ghi kết quả ...
        return
    dfs_top_down(node.left, new_state)
    dfs_top_down(node.right, new_state)


# 3) Iterative DFS bằng stack
def dfs_iter(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        # ... visit node ...
        stack.append(node.right)
        stack.append(node.left)     # left lên top trước

Bài tự luyện cuối chương

LC 100 - Same Tree
LC 101 - Symmetric Tree
LC 110 - Balanced Binary Tree
LC 124 - Binary Tree Maximum Path Sum (Chương 22)
LC 129 - Sum Root to Leaf Numbers
LC 144 - Binary Tree Preorder Traversal (iterative)
LC 257 - Binary Tree Paths

11.1 Maximum Depth of Binary Tree (LC 104)

Đề bài

Cho root của binary tree. Trả về độ sâu lớn nhất (số node trên path dài nhất từ root đến lá).

Ví dụ

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialize)

        Cây thực tế:
              3
             / \
            9   20
               /  \
              15   7

Output: 3

Ràng buộc

0 <= số node <= 10^4
-100 <= node.val <= 100

Clarifying questions

Cây 1 node? → Depth = 1.
Cây null? → Depth = 0.

Hướng tiếp cận

Bottom-up một dòng:

depth(node) = 1 + max(depth(left), depth(right)), base case rỗng → 0.

Code Python 3

class Solution:
    def maxDepth(self, root) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(h) stack (h = chiều cao).

Bình luận

Iterative BFS cũng làm được (đếm levels), nhưng DFS đệ quy đẹp nhất.
Bẫy: dùng +1 ngoài max(...) thay vì trong min/max - nếu phải tính min depth (LC 111), cần check None children cẩn thận (xem tự luyện).

Bài tự luyện liên quan

LC 111 - Minimum Depth of Binary Tree.
LC 543 - Diameter of Binary Tree.
LC 1448 - Count Good Nodes in Binary Tree.

11.2 Path Sum II (LC 113)

Đề bài

Cho root và số targetSum. Trả về tất cả đường đi root-to-leaf có tổng giá trị bằng targetSum.

Ví dụ

Input:  root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
        targetSum = 22

        Cây thực tế:
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1

Output: [[5,4,11,2], [5,8,4,5]]

Ràng buộc

0 <= số node <= 5000
-1000 <= node.val, targetSum <= 1000

Clarifying questions

Path từ root đến lá strict? → Có, không tính path partial.
Có thể có path rỗng (root null)? → Return [].

Hướng tiếp cận

DFS top-down + backtracking: - Đi xuống mỗi node, giảm target còn lại và append node vào path. - Tại leaf: nếu target == leaf.val → copy path vào kết quả. - Khi quay lên (sau khi duyệt xong các con) → path.pop() để khôi phục trạng thái.

Hình minh hoạ - đường đi 5 → 4 → 11 → 2 cho target = 22:

DFS(5, target=22, path=[]):
  path=[5], remaining=17
  DFS(4, 17):
    path=[5,4], remaining=13
    DFS(11, 13):
      path=[5,4,11], remaining=2
      DFS(7, 2):  leaf, 7 != 2 → bỏ
                  pop → path=[5,4,11]
      DFS(2, 2):  leaf, 2 == 2 → ADD [5,4,11,2] vào result
                  pop → path=[5,4,11]
      pop → path=[5,4]
    pop → path=[5]
  ...

Code Python 3

from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional["TreeNode"], targetSum: int) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def dfs(node, remaining: int) -> None:
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(path.copy())
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()                  # backtrack

        dfs(root, targetSum)
        return result

Phân tích độ phức tạp

Thời gian: O(n²) worst - copy mỗi path tốn O(h), có thể có O(n) paths.
Bộ nhớ: O(h) stack + path.

Bình luận

Bẫy thường gặp:
- Quên path.copy() → mọi entry trong result trỏ vào cùng list.
- Quên path.pop() cuối cùng → state dirty.
Liên kết với Chương 28 (Backtracking): cùng pattern path + undo.

Bài tự luyện liên quan

LC 112 - Path Sum (chỉ check có / không).
LC 437 - Path Sum III (path bất kỳ, dùng prefix sum).
LC 257 - Binary Tree Paths.

11.3 All Paths From Source to Target (LC 797)

Đề bài

Cho DAG graph (mảng adjacency list, node i có hàng xóm graph[i]). Trả về tất cả đường đi từ node 0 đến node n - 1.

Ví dụ

Input:  graph = [[1,2],[3],[3],[]]
        # đồ thị:  0 → 1 → 3
        #          0 → 2 → 3
Output: [[0,1,3], [0,2,3]]

Ràng buộc

2 <= n <= 15
Graph là DAG, không có chu trình.

Clarifying questions

Có thể không có path nào? → DAG luôn có (nếu reachable). Nếu không liên thông → list rỗng.

Hướng tiếp cận

DAG ⇒ không có chu trình ⇒ không cần visited. DFS từ 0, mỗi đến n-1 ghi path.

Code Python 3

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        result: list[list[int]] = []
        path: list[int] = [0]

        def dfs(node: int) -> None:
            if node == n - 1:
                result.append(path.copy())
                return
            for nb in graph[node]:
                path.append(nb)
                dfs(nb)
                path.pop()

        dfs(0)
        return result

Phân tích độ phức tạp

Thời gian: O(2^n · n) worst (DAG có thể có exponential paths).
Bộ nhớ: O(n) stack.

Bình luận

Vì sao không cần visited? DAG → không lặp lại node đã thăm trong cùng một path khi DFS. (Trên graph chung, phải check visited để tránh chu trình.)
Iterative: stack chứa (node, path) - nhưng phải clone path nên overhead.

Bài tự luyện liên quan

LC 332 - Reconstruct Itinerary.
LC 1971 - Find if Path Exists in Graph.

11.4 Validate Binary Search Tree (LC 98)

Đề bài

Cho root. Kiểm tra cây có phải BST hợp lệ không, theo định nghĩa: - Mọi node con trái: value strictly less than node hiện tại. - Mọi node con phải: value strictly greater than node hiện tại. - Cả 2 subtree đều là BST.

Ví dụ

Input:  root = [2, 1, 3]
        Cây thực tế:
              2
             / \
            1   3
Output: true

Input:  root = [5, 1, 4, null, null, 3, 6]
        Cây thực tế:
              5
             / \
            1   4
               / \
              3   6
Output: false
        (node 3 ở subtree phải của 5, nhưng 3 < 5 → vi phạm BST)

Ràng buộc

1 <= số node <= 10^4
-2^31 <= node.val <= 2^31-1

Clarifying questions

Tree có thể có duplicate value? → Theo đề BST chuẩn: không.
Tree rỗng? → True.

Hướng tiếp cận

Cách sai phổ biến - chỉ check node.left.val < node.val < node.right.val. Sai vì BST yêu cầu TOÀN BỘ subtree trái < node, không chỉ child trực tiếp.

Ví dụ ngược:

Tại node 5: 4 < 5 (OK), 1 < 5 (OK). Tại node 4: 3 < 4 < 6 (OK). Local check pass, nhưng 3 < 5 trong subtree phải → sai.

Cách đúng - DFS truyền (low, high) bound:

dfs(node, low, high): node phải thoả low < node.val < high. Khi đi xuống: - Trái: bound mới (low, node.val). - Phải: bound mới (node.val, high).

Cách 2 - Inorder traversal phải sắp xếp tăng strict.

BST inorder = sequence sorted. Duyệt inorder, kiểm tra mỗi value > value trước.

Code Python 3

import math
from typing import Optional

class Solution:
    """Cách 1 - DFS với bound (low, high)."""

    def isValidBST(self, root: Optional["TreeNode"]) -> bool:

        def dfs(node, low: float, high: float) -> bool:
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return dfs(node.left, low, node.val) and \
                   dfs(node.right, node.val, high)

        return dfs(root, -math.inf, math.inf)


class SolutionInorder:
    """Cách 2 - inorder traversal."""

    def isValidBST(self, root) -> bool:
        self.prev = -math.inf

        def inorder(node) -> bool:
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= self.prev:
                return False
            self.prev = node.val
            return inorder(node.right)

        return inorder(root)

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(h) stack.

Bình luận

Bẫy <= vs <: BST chuẩn cấm duplicate, dùng strict <. Một số biến thể cho phép duplicate ở một bên - phải hỏi rõ.
Inorder vs bound: inorder đẹp về toán, bound đẹp về code. Bound còn dễ extend nếu định nghĩa BST mở rộng (bằng nhau bên trái, …).

Bài tự luyện liên quan

LC 99 - Recover Binary Search Tree (Chương 22).
LC 700 - Search in a Binary Search Tree.
LC 230 - Kth Smallest Element in a BST.

11.5 House Robber III (LC 337)

Đề bài

Cho root của binary tree (LC level-order serialize, vd [3,2,3,null,3,null,1]). Nhà ở mỗi node có giá trị node.val. Tên trộm không thể trộm 2 nhà kề nhau (parent ↔︎ child). Trả về số tiền tối đa trộm được.

Ví dụ

Input:  root = [3, 2, 3, null, 3, null, 1]
        Cây thực tế:
              3
             / \
            2   3
             \   \
              3   1
Output: 7
        (trộm 3 + 3 + 1 = 7)

Input:  root = [3, 4, 5, 1, 3, null, 1]
        Cây thực tế:
              3
             / \
            4   5
           / \   \
          1   3   1
Output: 9
        (trộm 4 + 5 = 9)

Ràng buộc

1 <= số node <= 10^4
0 <= node.val <= 10^4

Clarifying questions

Tree rỗng? → 0.

Hướng tiếp cận

DP trên cây - mỗi node trả về 2 giá trị: - rob_this = max tiền nếu trộm node này (con không trộm). - skip_this = max tiền nếu không trộm node này (con tuỳ ý).

Quan hệ: - `rob_this = node.val + left.skip + right.skip`

skip_this = max(left.rob, left.skip) + max(right.rob, right.skip)

Đáp án = max(root.rob, root.skip).

Hình minh hoạ:

       3
      / \
     2   3
      \   \
       3   1

DFS bottom-up:
  node 3 (lá phải-phải): rob=3, skip=0
  node 3 (lá phải-trái): rob=3, skip=0
  node 1 (lá phải-phải-right): rob=1, skip=0

  node 2: rob = 2 + 0 (no left) + 0 (3 skip) = 2
          skip = 0 + max(3, 0) = 3
  node 3 (right): rob = 3 + max(0, 0)(no left) + 0 = 3
                  skip = 0 + max(1, 0) = 1

  node 3 (root): rob = 3 + 3 (no rob của 2) + 1 (no rob của 3-right) = 7
                 skip = max(2,3) + max(3,1) = 3 + 3 = 6

Đáp án: max(7, 6) = 7

Code Python 3

from typing import Optional, Tuple

class Solution:
    def rob(self, root: Optional["TreeNode"]) -> int:

        def dfs(node) -> Tuple[int, int]:
            """Trả về (rob_this, skip_this)."""
            if not node:
                return 0, 0
            l_rob, l_skip = dfs(node.left)
            r_rob, r_skip = dfs(node.right)
            rob_this = node.val + l_skip + r_skip
            skip_this = max(l_rob, l_skip) + max(r_rob, r_skip)
            return rob_this, skip_this

        return max(dfs(root))

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(h) stack.

Bình luận

Tại sao không dùng memo dfs(node, robbed_parent: bool)? Hoàn toàn được, nhưng cần 2n state. Pattern “trả tuple 2 giá trị” gọn hơn và tránh dùng @cache (vốn không hash được TreeNode mặc định).
Pattern Tree DP sẽ tái xuất nhiều trong Chương 42.

Bài tự luyện liên quan

LC 198 - House Robber (1D).
LC 213 - House Robber II (vòng tròn).
LC 968 - Binary Tree Cameras (cùng tinh thần state-per-node).

11.6 Lowest Common Ancestor of a Binary Tree (LC 236)

Đề bài

Cho root của binary tree (không phải BST) và 2 node p, q. Tìm lowest common ancestor (LCA) - node thấp nhất có cả p và q trong subtree của nó.

Ví dụ

Input:  root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
        Cây thực tế:
              3
             / \
            5   1
           / \ / \
          6  2 0  8
            / \
           7   4

Input:  p = 5, q = 1   → Output: 3
Input:  p = 5, q = 4   → Output: 5   (5 là tổ tiên của chính nó)

Ràng buộc

2 <= số node <= 10^5
node.val distinct

Clarifying questions

p, q chắc chắn trong cây? → Theo LC: có.
p == q? → LCA = chính nó.

Hướng tiếp cận

Insight tinh tế: Tại mỗi node: - Nếu node == p hoặc node == q → trả về node luôn. - Đệ quy trên left và right. - Nếu cả 2 đệ quy đều trả về non-None → node là LCA. - Nếu chỉ 1 cái trả non-None → trả cái đó (nghĩa là cả p và q đều ở 1 bên).

Code Python 3

from typing import Optional

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root          # p và q ở 2 nhánh → root là LCA
        return left if left else right

Phân tích độ phức tạp

Thời gian: O(n). Bộ nhớ: O(h) stack.

Bình luận

Vì sao gọn vậy? Hàm trả về node tổ tiên đầu tiên gặp được. Nếu cả 2 subtree đều “có ai đó”, đó là LCA; ngược lại đáp án nằm hoàn toàn ở 1 bên.
Bẫy: root is p (so sánh reference) thay vì root.val == p.val - nếu cây có duplicate values, val-comparison sẽ sai.
Follow-up:
- LC 235 - LCA of BST: tận dụng property BST, O(h) ngắn gọn.
- LC 1644 - LCA II: p hoặc q có thể không tồn tại - phải kiểm tra cẩn thận.
- LC 1650 - LCA III: node có pointer parent → giống Intersection of LL.

Bài tự luyện liên quan

LC 235 - LCA of BST.
LC 1644 - LCA II.
LC 1650 - LCA III (with parent pointer).

Tóm tắt chương & Quyết định

Traversal order cheat sheet

Traversal	Khi nào dùng
Pre-order (root → L → R)	Serialize, clone, copy
In-order (L → root → R)	BST sorted output, kth smallest
Post-order (L → R → root)	Tổng hợp từ con (tree DP, diameter)
Level-order (BFS)	Theo tầng, distance

DFS return value design (cốt lõi tree DP)

def dfs(node):
    if not node: return base
    L = dfs(node.left)
    R = dfs(node.right)
    # combine L, R với node.val → ans cho subtree này
    # CẬP NHẬT đáp số toàn cục nếu cần
    return result_to_pass_up

Cẩn thận: cái trả về ≠ cái đáp số toàn cục (ví dụ Diameter trả về depth, đáp số là max gather).

Validate BST - global bounds

Sai: chỉ kiểm left.val < root.val < right.val.
Đúng: truyền (lo, hi); mỗi node phải nằm trong (lo, hi). Sang trái cập nhật hi = node.val, sang phải cập nhật lo = node.val.

House Robber III - `(rob, skip)` trace

Cây:

Post-order trả về (rob_this, skip_this): - Lá 3 (left của 2): (3, 0). - Lá 1 (right của 3): (1, 0). - Node 2: rob = 2 + 0 = 2, skip = max(3,0) = 3 → (2, 3). - Node 3 (right of root): rob = 3 + 0 = 3, skip = max(1,0) = 1 → (3, 1). - Root 3: rob = 3 + 3 + 1 = 7, skip = max(2,3) + max(3,1) = 3 + 3 = 6 → max(7,6) = 7.

LCA variants - phân biệt

Loại cây	Cách
Binary tree thường	Đệ quy bottom-up, trả node nếu chứa p hoặc q (LC 236)
BST	So sánh value với root, đi 1 nhánh (LC 235) - O(log n)
Có parent pointer	Hash các tổ tiên của p, đi từ q lên