Maximum Depth of Binary Tree: chiều cao như một tính toán post-order

Định nghĩa của chiều sâu là đệ quy. Chiều sâu của một node bằng 1 cộng với chiều sâu tối đa của các con của nó. Câu đó đã chứa sẵn thuật toán rồi. Khi bạn thấy "tính toán thứ gì đó ở một node bằng cách dùng giá trị từ các con của nó," bạn đang nhìn vào một post-order traversal — xử lý con trước, rồi dùng kết quả của chúng ở node cha. Invert Binary Tree (226) hoạt động theo cùng cách đó: swap các con, rồi trả về node. Maximum depth có cùng hình dạng, chỉ là số học thay vì swap.

Constraints ở đây nhẹ nhàng: tối đa 10^4 node, giá trị từ -100 đến 100. Giá trị node không quan trọng gì cả — bạn đang đo cấu trúc, không phải nội dung. Cây có thể rỗng (root là null), trả về 0. Với 10^4 node, bất kỳ giải pháp O(n) nào cũng ổn. Điểm áp lực duy nhất là space: cây hoàn toàn skewed có chiều cao n, đặt O(n) frame lên call stack với recursive approach.

Post-order là sự lựa chọn tự nhiên

Một node không thể biết chiều cao của chính nó cho đến khi cả hai cây con báo cáo chiều cao của chúng. Sự phụ thuộc đó buộc phải có thứ tự: cây con trái trước, cây con phải sau, rồi node hiện tại tính 1 + max(left, right). Đó là post-order. Bạn không chọn post-order vì nó thanh lịch — bạn chọn nó vì luồng thông tin của bài toán không cho phép lựa chọn nào khác.

Theo dõi [3, 9, 20, null, null, 15, 7] để thấy điều này. Các giá trị chiều cao nổi lên từ các leaf:

Node 9 là leaf: không có con, nên max(0, 0) = 0, depth 1 + 0 = 1. Node 15 là leaf: depth 1. Node 7 là leaf: depth 1. Node 20 có các con báo depth 1 và 1: 1 + max(1, 1) = 2. Root 3 có 9 (depth 1) và 20 (depth 2): 1 + max(1, 2) = 3. Kết quả lan từ các leaf lên trên. Root là node cuối cùng được giải quyết — đó chính là post-order.

Ví dụ thứ hai: [1, null, 2]. Root 1 không có con trái (depth 0) và có con phải 2 (leaf, depth 1): 1 + max(0, 1) = 2. Đúng.

Recursive DFS

Version đệ quy là hai trường hợp, một dòng số học:

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

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);
        return 1 + Math.Max(leftDepth, rightDepth);
    }
}

Base case: null trả về 0. Mọi thứ khác chỉ là một dòng. Thứ tự quan trọng: bạn giải quyết left_depth hoàn toàn trước khi chạm vào right_depth. Đó là sự phụ thuộc post-order đang diễn ra — call stack của function đang làm bookkeeping cho bạn.

Time: O(n) — mỗi node được thăm đúng một lần. Space: O(h), với h là chiều cao của cây. Trên cây cân bằng là O(log n). Trên cây hoàn toàn skewed — mỗi node chỉ có một con phải, về cơ bản là linked list — là O(n), và call stack tăng trưởng tương ứng. Với constraint của LeetCode là tối đa 10^4 node, cây skewed tối đa chạy 10,000 recursive call sâu. Recursion limit mặc định của Python là 1,000. Nếu bạn đang dùng Python và ai đó xây dựng worst case đó, solution đệ quy sẽ fail. Đây không phải là lo lắng lý thuyết cho bài này cụ thể (judge không tạo ra chuỗi 10^4 node), nhưng đáng biết.

Đây là version tôi sẽ viết đầu tiên và, hầu hết thời gian, ship.

Iterative DFS

Version iterative sao chép cùng traversal — sử dụng explicit stack thay vì call stack. Mẹo: lưu các cặp (node, current_depth). Khi bạn pop một node, bạn đã biết depth của nó rồi.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [(root, 1)]
        max_depth = 0
        while stack:
            node, depth = stack.pop()
            max_depth = max(max_depth, depth)
            if node.left:
                stack.append((node.left, depth + 1))
            if node.right:
                stack.append((node.right, depth + 1))
        return max_depth

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        var stack = new Stack<(TreeNode node, int depth)>();
        stack.Push((root, 1));
        int maxDepth = 0;
        while (stack.Count > 0) {
            var (node, depth) = stack.Pop();
            maxDepth = Math.Max(maxDepth, depth);
            if (node.left != null)  stack.Push((node.left,  depth + 1));
            if (node.right != null) stack.Push((node.right, depth + 1));
        }
        return maxDepth;
    }
}

Theo dõi ví dụ đó với approach này. Stack bắt đầu là [(3, 1)]. Pop (3, 1): max_depth = 1, push (9, 2) và (20, 2). Pop (20, 2): max_depth = 2, push (15, 3) và (7, 3). Pop (7, 3): max_depth = 3, không có con. Pop (15, 3): max_depth vẫn 3. Pop (9, 2): max_depth vẫn 3. Stack rỗng, trả về 3.

Thứ tự traversal ở đây không thực sự là post-order — nó là pre-order, vì bạn xử lý node khi pop thay vì sau khi các con của nó. Điều đó không quan trọng ở đây. Bạn không tính toán bottom-up; bạn chỉ theo dõi depth tối đa thấy được dọc theo bất kỳ đường root-to-leaf nào. Pre-order cho cùng kết quả.

Cùng time complexity với version đệ quy: O(n). Space cũng là O(h) trong worst case — stack chứa nhiều nhất một đường từ root đến leaf tại một thời điểm. Điểm khác biệt: đây là heap-allocated stack, không phải native call stack, nên recursion limit của Python không áp dụng. An toàn cho cây skewed ở bất kỳ kích thước nào.

BFS: đếm level

BFS tiếp cận từ một góc nhìn khác. Thay vì hỏi "chiều sâu tối đa của các cây con của root là bao nhiêu?", nó hỏi "cây có bao nhiêu level?" Đó là những câu hỏi tương đương với các mental model khác nhau. Nếu bạn hình dung cây như các tầng, BFS là bản dịch trực quan hơn.

from collections import deque
 
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([root])
        depth = 0
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int depth = 0;
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                if (node.left != null)  queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            depth++;
        }
        return depth;
    }
}

Theo dõi [3, 9, 20, null, null, 15, 7]:

• Level 1: queue = [3], xử lý 3, push 9 và 20. depth = 1.
• Level 2: queue = [9, 20], xử lý 9 (không có con), xử lý 20 (push 15 và 7). depth = 2.
• Level 3: queue = [15, 7], xử lý cả hai (không có con). depth = 3.
• Queue rỗng, trả về 3.

Pattern snapshot — capture len(queue) lúc bắt đầu vòng lặp mỗi level — là BFS level-processing idiom. Mọi node ở level hiện tại được dequeue trước khi tiếp tục. depth tăng một lần mỗi level, không phải mỗi node.

Time: O(n). Space: O(w), với w là độ rộng tối đa của cây. Với complete binary tree, level cuối cùng chứa khoảng n/2 node, nên worst-case space là O(n). Với cây skewed, mỗi level có một node và queue không bao giờ chứa nhiều hơn hai node cùng lúc — O(1). BFS an toàn hơn cho cây cao, hẹp; recursive DFS gặp rủi ro hơn với cây rộng, nông.

So sánh các approach

Cả ba đều O(n) time. Trade-off space phụ thuộc vào hình dạng cây và approach được chọn. Recursive DFS ngắn nhất. Iterative DFS là drop-in an toàn khi recursion có vấn đề. BFS tỏa sáng khi bạn cần xử lý từng level.

Các edge case đáng chú ý

Cây rỗng (root = null): cả ba approach trả về 0 ngay lập tức. Đây là edge case bắt buộc duy nhất thực sự cần xử lý — mọi approach đều phải handle nó tường minh, và quên đi sẽ gây null pointer error.

Một node duy nhất: root không có con. Recursive: 1 + max(0, 0) = 1. Iterative DFS: pop (root, 1), không có con để push, trả về 1. BFS: xử lý một level, trả về 1. Tất cả đều đúng.

Cây skewed (tất cả node chuỗi về một phía): chiều cao bằng số node. Đây là worst case cho cả hai DFS approach (O(n) space). BFS xử lý trong O(1) space vì mỗi level có một node. Recursive DFS sẽ hit recursion limit của Python nếu cây đủ sâu.

Complete binary tree: tất cả leaf ở cùng level. BFS worst case — level cuối cùng có n/2 node, tất cả trong queue cùng lúc.

Bài toán xác nhận giá trị node trong [-100, 100]. Điều này không liên quan — thuật toán không bao giờ kiểm tra giá trị. Đây là cái bẫy thường gặp khi đọc constraints lần đầu.

Nhận diện bài toán

Dùng cấu trúc post-order DFS này khi bài toán là "tính một thuộc tính của node bằng thuộc tính của cây con của nó." Maximum depth, minimum depth, diameter, kiểm tra cân bằng, subtree sum — tất cả theo cùng hình dạng đó. Return value của recursion mang thông tin bottom-up; node cha kết hợp chúng lại.

Dùng BFS khi bài toán liên quan đến xử lý node theo từng level. Level order traversal, tìm node ở depth cụ thể, tính trung bình từng level — tất cả dùng pattern snapshot-len(queue) mà bạn thấy trong BFS solution ở trên.

Keywords báo hiệu bài toán này: "maximum depth," "height of tree," "number of levels," "deepest node," "longest path from root to leaf."

Tiếp theo là gì

Diameter of Binary Tree (543) là follow-up trực tiếp nhất. Diameter của cây là đường dài nhất giữa bất kỳ hai node nào. Đường đó đi qua một node "pivot" nào đó và dùng chiều cao của cây con trái và phải của nó: left_height + right_height. Bạn đang tính chiều cao tại mỗi node trong post-order pass — chính xác là thứ bạn đã viết ở đây — và theo dõi max sum thay vì max single value. Một thay đổi nhỏ từ code này.

Balanced Binary Tree (110) dùng cùng hình dạng post-order. Cây cân bằng nếu tại mỗi node, cây con trái và phải chênh lệch chiều cao tối đa 1. Tính chiều cao trong post-order pass, kiểm tra điều kiện cân bằng, lan truyền chiều cao lên — hoặc giá trị sentinel (-1) nếu cây con đã mất cân bằng. Cùng skeleton, bookkeeping khác.

Minimum Depth of Binary Tree (111) là bài gần giống nhất. Minimum depth là số node trên đường ngắn nhất từ root đến leaf. Cái bẫy: min(left, right) không hoạt động trực tiếp khi một cây con rỗng — bạn sẽ lấy 0, nhưng đó không phải leaf. Bạn cần min của các depth con khác 0 khi node chỉ có một con.

Binary Tree Level Order Traversal (102) lấy cấu trúc BFS ở đây và thêm một thứ: thay vì bỏ qua các node của mỗi level sau khi xử lý, thu thập chúng vào một hàng. Quản lý queue giống hệt nhau; format output phong phú hơn.

Maximum Depth of N-ary Tree (559) là tổng quát hóa trực tiếp. Thay vì hai con, mỗi node có danh sách con tùy ý. Recursive case trở thành 1 + max(maxDepth(child) for child in root.children). Cấu trúc giống nhau; chỉ thay đổi một dòng code.

Cả năm bài đều theo cùng traversal pattern bạn đã thấy ở đây. Các primitive không thay đổi — chỉ là những gì bạn tích lũy trên đường đi.