Đường kính Binary Tree: khi đường đi dài nhất tránh qua root

Diameter là đường đi dài nhất giữa hai node bất kỳ, đo bằng số cạnh. Đường đi đó có thể đi qua root — hoặc có thể nằm hoàn toàn trong một subtree, bỏ qua sự tồn tại của root. Câu ghi chú "may or may not pass through the root" trong đề bài không phải là chi tiết phụ; đó là thách thức thiết kế cốt lõi.

Trong cây này, đường đi dài nhất là 4 -> 2 -> 1 -> 3 (hoặc 5 -> 2 -> 1 -> 3), tức là 3 cạnh. Nó có đi qua root. Nhưng hãy hình dung một cây mà subtree sâu nhất nằm hoàn toàn dưới node con trái — root chỉ là người ngoài cuộc.

Insight cốt lõi: tại bất kỳ node nào, diameter đi qua node đó bằng depth của subtree trái cộng depth của subtree phải. Diameter toàn cục là giá trị lớn nhất của con số đó trên tất cả các node. Mọi thứ đều xuất phát từ đây.

Đề bài

Cho root của một binary tree, trả về độ dài diameter — đường đi dài nhất tính bằng số cạnh giữa hai node bất kỳ. Đường đi có thể đi qua root hoặc không; độ dài được tính bằng số cạnh, không phải số node. Đề bài đầy đủ: LeetCode 543.

Ràng buộc:
- Số lượng node trong cây nằm trong khoảng [1, 10^4].
- -100 <= Node.val <= 100

Constraints nói gì

Bài toán đảm bảo [1, 10^4] node và giá trị trong [-100, 100]. Dải giá trị không ảnh hưởng gì cả — thuật toán chỉ quan tâm đến cấu trúc, không bao giờ cần đến giá trị. Số lượng node thì quan trọng.

10^4 node đủ lớn để một giải pháp O(n^2) cảm nhận được — gọi hàm depth cho mỗi node nghĩa là tối đa 10^8 phép toán trong trường hợp xấu nhất (chuỗi lệch hoàn toàn). Con số đó có thể TLE trên một judge nghiêm ngặt. Constraint này đang ngầm thúc đẩy bạn hướng tới một lần duyệt tuyến tính.

Giới hạn dưới 1 node đáng chú ý: câu trả lời nhỏ nhất có thể là 0 (một node đơn không có cạnh nào), và code phải trả về 0 một cách tự nhiên mà không cần xử lý đặc biệt.

Độ sâu recursion: trong trường hợp xấu nhất (chuỗi lệch trái hoàn toàn gồm 10^4 node), call stack DFS sâu 10^4 cấp. Giới hạn recursion mặc định của Python là 1000, nên một giải pháp đệ quy đơn giản sẽ gặp RecursionError với đầu vào cực đoan. Trong bối cảnh contest/phỏng vấn điều này thường bị bỏ qua, nhưng đáng biết. C# có stack mặc định lớn hơn nhiều và không gặp vấn đề này.

Approach 1: Brute force — tính lại depth tại mỗi node

Cách đọc trực tiếp: duyệt qua mọi node, tính depth của subtree trái và phải tại node đó, cộng lại, giữ giá trị lớn nhất. Hai lần duyệt cho mỗi node — một để đi qua tất cả các node, một để tính depth từ mỗi node.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
 
        max_diameter = 0
 
        def get_depth(node: TreeNode) -> int:
            if not node:
                return 0
            return 1 + max(get_depth(node.left), get_depth(node.right))
 
        def traverse(node: TreeNode) -> None:
            nonlocal max_diameter
            if not node:
                return
            left_depth = get_depth(node.left)
            right_depth = get_depth(node.right)
            max_diameter = max(max_diameter, left_depth + right_depth)
            traverse(node.left)
            traverse(node.right)
 
        traverse(root)
        return max_diameter

public class Solution {
    private int maxDiameter = 0;
 
    public int DiameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        maxDiameter = 0;
        Traverse(root);
        return maxDiameter;
    }
 
    private int GetDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.Max(GetDepth(node.left), GetDepth(node.right));
    }
 
    private void Traverse(TreeNode node) {
        if (node == null) return;
        int leftDepth = GetDepth(node.left);
        int rightDepth = GetDepth(node.right);
        maxDiameter = Math.Max(maxDiameter, leftDepth + rightDepth);
        Traverse(node.left);
        Traverse(node.right);
    }
}

Cách này đúng, nhưng nó tính lại depth của mọi descendant cho mọi ancestor. Node 4 trong ví dụ trên có depth được tính khi bạn gọi get_depth từ node 2, rồi tính lại khi gọi từ node 1. Với cây cân bằng đó là O(n log n); với chuỗi lệch thì đạt O(n^2).

Time: O(n^2). Mỗi trong n node kích hoạt một lần duyệt depth đầy đủ của subtree của nó.

Space: O(n) cho call stack — hai lời gọi đệ quy đồng thời, cả hai sâu tối đa O(h), với h là chiều cao cây.

Approach 2: DFS tối ưu — depth và diameter trong một lần duyệt

Sự lãng phí trong brute force rõ ràng ngay khi bạn nhìn thấy nó: get_depth đi lại các subtree đã được duyệt rồi. Cách sửa cũng rõ ràng tương đương — để mỗi lời gọi DFS trả về depth của chính nó, để node cha không bao giờ cần tính lại.

Đây là post-order traversal. Bạn xử lý con trước, thu thập depth của chúng, sau đó tính diameter tại node hiện tại bằng các depth đã biết. Không có công việc thừa.

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diameter = 0
 
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)
            # diameter qua node này = cánh tay trái + cánh tay phải
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            # trả depth lên cho node cha — họ cộng thêm 1 cho cạnh tới node này
            return 1 + max(left_depth, right_depth)
 
        dfs(root)
        return self.max_diameter

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

Time: O(n). Mỗi node được thăm đúng một lần. Tại mỗi lần thăm công việc là O(1) — hai lời gọi đệ quy (đã được tính), một max, một phép cộng, một phép so sánh.

Space: O(h) trong đó h là chiều cao cây. Cây cân bằng: O(log n). Chuỗi lệch: O(n). Độ sâu call stack bị giới hạn bởi h, và biến diameter sống trên heap (Python self, C# field).

Trace tay qua root = [1, 2, 3, 4, 5]

Đi theo DFS post-order — con trước, cha sau:

dfs(4):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(5):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(2):  left=1 (từ node 4), right=1 (từ node 5)
         diameter candidate: 1+1=2  -> max_diameter = 2
         return 1+max(1,1) = 2

dfs(3):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(1):  left=2 (từ node 2), right=1 (từ node 3)
         diameter candidate: 2+1=3  -> max_diameter = 3
         return 1+max(2,1) = 3

Kết quả: max_diameter = 3

Giá trị max được cập nhật hai lần: đầu tiên là 2 tại node 2 (đường đi 4->2->5), sau đó là 3 tại node 1 (đường đi 4->2->1->3). Biến toàn cục tích lũy giá trị tốt nhất đã thấy — không có cách nào để "quay lại sửa" giá trị trước đó.

Các edge case quan trọng

Node đơn (root = [1]): dfs(1) gọi dfs(null) hai lần, cả hai trả về 0. Diameter candidate là 0+0=0. Trả về 1. max_diameter = 0. Đúng — không có cạnh nào tồn tại.

Hai node (root = [1, 2]): dfs(2) trả về 1. dfs(null) trả về 0. Tại node 1, candidate là 1+0=1. max_diameter = 1. Một cạnh, một diameter. Đúng.

Chuỗi tuyến tính (ví dụ 1->2->3->4): mỗi node chỉ có một con, không bao giờ có hai. Diameter không bao giờ được cập nhật vượt quá số node trên đường từ root đến lá — tức là n-1 cạnh. Tại mỗi node, left_depth + right_depth là k + 0 = k hoặc 0 + 0 = 0 tùy theo hướng chuỗi đi. Câu trả lời là n-1. Đúng.

Diameter trong subtree, không qua root: hình dung một subtree trái rất sâu với hai nhánh dài ở dưới cùng, và một subtree phải nhỏ xíu ở root. Giá trị left_depth + right_depth lớn nhất xảy ra tại node phân nhánh sâu trong subtree trái, không phải ở root. Biến toàn cục bắt được nó vì chúng ta cập nhật max_diameter tại mọi node, không chỉ ở root.

Root null: bài toán đảm bảo ít nhất 1 node, nên root = null về mặt kỹ thuật nằm ngoài giới hạn. Nhưng cả hai implementation vẫn trả về 0 an toàn nếu được truyền null — dfs(null) trả về 0 ngay lập tức, max_diameter giữ nguyên 0.

Pattern: post-order accumulation với side-channel result

Bài toán này là ví dụ rõ ràng nhất về một pattern xuất hiện xuyên suốt các bài toán tree: bạn muốn tính toán điều gì đó tại mỗi node phụ thuộc vào kết quả của con, nhưng đồng thời bạn cũng muốn tích lũy một giá trị tốt nhất toàn cục trong quá trình đó. Hàm đệ quy phục vụ hai mục đích cùng lúc — nó trả về metric cục bộ (depth, ở đây) lên cho node cha, và cập nhật bộ tích lũy toàn cục (max_diameter) như một side effect.

Giá trị trả về cục bộ và bộ tích lũy toàn cục theo dõi những thứ khác nhau. Depth là "đường đi từ tôi xuống lá sâu nhất dài bao nhiêu." Diameter là "đường đi dài nhất đi qua tôi là bao nhiêu." Hàm trả về depth; nó cập nhật diameter. Cả hai xảy ra trong một lần duyệt.

Post-order DFS hai mục đích này xuất hiện ở:

• Binary Tree Maximum Path Sum (124): trả về lợi ích arm đơn tốt nhất lên trên; cập nhật path sum toàn cục tốt nhất (có thể span cả hai arm) như side effect. Cấu trúc gần như giống hệt 543 — thay "depth" bằng "max gain" và "số cạnh" bằng "tổng".
• Longest Univalue Path (687): trả về arm dài nhất với giá trị nhất quán; cập nhật đường đi dài nhất toàn cục như side effect. Cùng skeleton, predicate cục bộ khác.
• Balanced Binary Tree (110): trả về chiều cao lên trên; cập nhật flag "is balanced" như side effect. Bộ tích lũy chuyển thành boolean thay vì integer.

Khi bạn nhận ra hình dạng — trả về metric cục bộ lên, tích lũy best toàn cục sang bên — bạn nhận ra nó ngay lập tức.

Brute force vs. tối ưu: khoảng cách thực sự quan trọng khi nào?

Với những cây nhỏ, sự khác biệt O(n^2) vs. O(n) chỉ là lý thuyết. Với n = 10^4 và hình dạng cực đoan (chuỗi), brute force đạt khoảng 5 * 10^7 phép toán — chậm nhưng có thể nằm trong giới hạn thời gian rộng rãi. DFS tối ưu làm 10^4.

Cái tôi thực sự sẽ ship: DFS tối ưu, không do dự. Code không khó hiểu hơn brute force — thực ra tôi thấy nó gọn gàng hơn, vì logic "tính depth, cập nhật diameter" sống ở một nơi thay vì bị phân tách giữa hai hàm đệ quy riêng biệt. Ưu điểm duy nhất của brute force là hai mối lo (duyệt và depth) được tách biệt về mặt thị giác, điều này có thể giúp khi bạn lần đầu lý luận về bài toán. Khi bạn đã thuyết phục được rằng nó đúng, việc gộp hai thứ vào một lần duyệt là một refactor đơn giản.

Bảng so sánh

Vị trí trong series trees

Đây là bài thứ chín trong series. Các bài trước đã xây dựng từ vựng: Maximum Depth (104) dạy pattern tính depth mà brute-force 543 tái sử dụng trực tiếp. Invert Binary Tree (226) và Same Tree (100) chỉ ra rằng post-order DFS là cách tự nhiên để kết hợp kết quả của con tại node cha. Subtree of Another Tree (572) và Validate BST (98) thêm các flag side-channel vào giá trị trả về DFS.

543 là bài đầu tiên trong series này mà câu trả lời không được trả về trực tiếp từ DFS — nó được tích lũy toàn cục trong khi DFS trả về một đại lượng khác (depth). Sự tách biệt đó là bước khái niệm mà bài toán này đang dạy.

Binary Tree Maximum Path Sum (124) là người hàng xóm trực tiếp khó nhất: cùng pattern post-order accumulation, nhưng depth trở thành "gain từ một arm subtree" và bạn phải xử lý đúng các giá trị âm (bạn có thể chọn loại bỏ một arm nếu đóng góp của nó là âm). Hình dạng của giải pháp gần như giống hệt; độ khó đến từ việc lý luận về các gain âm.

Longest Univalue Path (687) thêm ràng buộc giá trị: đường đi phải gồm các node có cùng giá trị. Post-order accumulation vẫn giữ nguyên, nhưng độ dài arm reset về 0 khi giá trị thay đổi.

Count Good Nodes in Binary Tree (1448) có hương vị khác: bạn truyền một giá trị maximum xuống dưới (pre-order) thay vì tích lũy lên trên (post-order). Đây là ví dụ phản chiều tốt để nghiên cứu sau 543, vì chiều của dòng thông tin bị đảo ngược.

Diameter of N-ary Tree (1522) tổng quát hóa trực tiếp: thay vì con trái và con phải, mỗi node có một danh sách con tùy ý. Bạn lấy hai arm dài nhất và cộng chúng lại. Cùng post-order DFS hai mục đích, được tổng quát hóa.