Binary Tree Maximum Path Sum: thủ thuật hai path khiến O(N) trở nên khả thi

bởi Duong Tran Quang aka DTDucas14 tháng 6, 2026 · 13 phút đọc#000781 lượt đọc#trees#dfs#dynamic-programming#recursion#leetcode#post-order

Chưa có đánh giáĐăng nhập để đánh giá

Path trong bài toán này không cần đi qua root, không cần chạy từ lá đến lá, và có thể uốn cong — nghĩa là một node có thể là đỉnh của path đi xuống cả hai subtree trái và phải. Đặc điểm cuối cùng đó mới là bẫy thật sự. Một DFS bình thường tính một giá trị cho mỗi node rồi trả về cho cha. Ở đây bạn cần hai giá trị tại mỗi node cùng lúc: cái bạn trả về cho cha (một cánh tay đi xuống), và cái bạn ghi lại cho global answer (có thể là path cong mà bạn không thể mở rộng thêm). Lẫn lộn hai thứ này là nguồn gốc của mọi lỗi sai.

Constraints đặt bối cảnh. n lên đến 3 * 10^4, nên O(N^2) đã chặt và O(N^3) hoàn toàn loại. Giá trị node nằm trong [-1000, 1000], tức là giá trị âm rất phổ biến — bạn có thể có cây cân bằng hoàn hảo mà path tối ưu chỉ là một node lá duy nhất. Bài toán đảm bảo ít nhất một node, nên khởi tạo global max bằng âm vô cực rồi trả về luôn an toàn.

Đề bài

Cho root của một binary tree, tìm path sum lớn nhất trên bất kỳ path nào không rỗng — trong đó path là chuỗi node liên kết qua các cạnh, mỗi node xuất hiện tối đa một lần, và path không cần đi qua root hay chạy từ lá đến lá. Đề gốc: LeetCode 124.

text

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

Tại sao approach hiển nhiên nhất không hoạt động

Cách đọc hiển nghĩa nhất của "thử tất cả path" sẽ là: liệt kê mọi cặp node (hoặc mọi node làm đỉnh tiềm năng), tính tổng path qua node đó, rồi theo dõi maximum. Đây là O(N^3) trong trường hợp tệ nhất — O(N) đỉnh ứng cử, O(N) để tính cánh tay trái tốt nhất từ mỗi đỉnh, O(N) cho cánh tay phải. Ngay cả với n = 10^4 thì con số là 10^12 phép toán. Không khả thi.

Một brute force thông minh hơn một chút: với mỗi node, chạy hai DFS — một vào subtree trái, một vào subtree phải — để tìm độ dài cánh tay tốt nhất, rồi kết hợp lại. Vẫn là O(N^2) vì bạn lặp lại công việc tìm cánh tay tại mọi node mà không cache gì cả.

Đây là skeleton brute-force bằng cả hai ngôn ngữ, viết ra để thấy rõ sự lãng phí:

python

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.result = float('-inf')
 
        def best_arm(node: Optional[TreeNode]) -> int:
            """Trả về cánh tay đơn dài nhất bắt đầu từ node, đi xuống dưới."""
            if not node:
                return 0
            left = max(0, best_arm(node.left))
            right = max(0, best_arm(node.right))
            return node.val + max(left, right)
 
        def check_all(node: Optional[TreeNode]) -> None:
            """Với mỗi node, tính lại cả hai cánh tay từ đầu và ghi nhận path cong."""
            if not node:
                return
            left = max(0, best_arm(node.left))
            right = max(0, best_arm(node.right))
            self.result = max(self.result, node.val + left + right)
            check_all(node.left)
            check_all(node.right)
 
        check_all(root)
        return self.result

csharp

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    private int result = int.MinValue;
 
    private int BestArm(TreeNode node) {
        if (node == null) return 0;
        int left = Math.Max(0, BestArm(node.left));
        int right = Math.Max(0, BestArm(node.right));
        return node.val + Math.Max(left, right);
    }
 
    private void CheckAll(TreeNode node) {
        if (node == null) return;
        int left = Math.Max(0, BestArm(node.left));
        int right = Math.Max(0, BestArm(node.right));
        result = Math.Max(result, node.val + left + right);
        CheckAll(node.left);
        CheckAll(node.right);
    }
 
    public int MaxPathSum(TreeNode root) {
        result = int.MinValue;
        CheckAll(root);
        return result;
    }
}

CheckAll thăm mọi node: O(N). Tại mỗi node nó gọi BestArm cho cả hai con, mỗi cái recurse qua toàn bộ subtree bên dưới: O(N) mỗi lần. Tổng: O(N^2). Với n = 3 * 10^4 đó là xấp xỉ 9 * 10^8 phép tính — tốt nhất là chập choạng, và constant không nhỏ vì recursion Python chậm. Cách này sẽ TLE trên LeetCode.

Sự lãng phí rõ ràng ngay khi nhìn thấy: BestArm cho con trái tại node X tính toán lại chính xác các giá trị cánh tay mà BestArm cho con trái tại cha của X cũng sẽ tính lại. Bạn đang duyệt subtree thừa ở mỗi level.

Approach	Time	Space
Brute force (two-pass DFS mỗi node)	O(N^2)	O(H)
DFS post-order (single pass)	O(N)	O(H)

H là chiều cao cây — O(log N) cho cây cân bằng, O(N) cho chuỗi lệch.

Insight then chốt: gộp hai phép tính vào một lần duyệt

Cách sửa là thực hiện tính toán cánh tay và cập nhật global trong cùng một DFS call, đồng thời. Đây là cách phân rã chính xác:

Tại mỗi node, định nghĩa hai giá trị:

Giá trị cánh tay — path tốt nhất bắt đầu từ node này và đi thẳng xuống vào một subtree (hoặc dừng ở đây). Đây là thứ bạn trả về cho cha. Cha chỉ có thể kéo dài một cánh tay xuống, không phải cả hai — nếu không path sẽ đi vòng qua node cha và mất tính liên tục.
Giá trị đỉnh — path tốt nhất mà node này là điểm cao nhất. Nó có thể dùng cả cánh tay trái lẫn cánh tay phải, vì path uốn cong ở đây và không cần đi lên nữa.

Giá trị đỉnh được gộp vào global maximum. Giá trị cánh tay được trả về cho caller. Bạn không bao giờ trả về giá trị đỉnh — làm vậy sẽ sai vì cha không thể mở rộng path cong thêm.

Trace tay [-10, 9, 20, null, null, 15, 7] theo thứ tự post-order (lá trước):

Node 15 (lá):

Cánh tay trái = 0, cánh tay phải = 0 (không có con)
Giá trị đỉnh = 0 + 15 + 0 = 15. Global max trở thành 15.
Trả về cánh tay = 15.

Node 7 (lá):

Cánh tay trái = 0, cánh tay phải = 0.
Giá trị đỉnh = 7. Global max vẫn là 15.
Trả về cánh tay = 7.

Node 20:

Cánh tay trái từ con = max(0, 15) = 15. Cánh tay phải từ con = max(0, 7) = 7.
Giá trị đỉnh = 15 + 20 + 7 = 42. Global max trở thành 42.
Trả về cánh tay = 20 + max(15, 7) = 35. (Chọn cánh tay đi xuống tốt hơn, không phải cả hai.)

Node 9 (lá):

Giá trị đỉnh = 9. Global max vẫn là 42.
Trả về cánh tay = 9.

Node -10 (root):

Cánh tay trái = max(0, 9) = 9. Cánh tay phải = max(0, 35) = 35.
Giá trị đỉnh = 9 + (-10) + 35 = 34. Global max vẫn là 42.
Trả về cánh tay = -10 + max(9, 35) = 25. (Không quan trọng — không ai dùng giá trị này.)

Đáp án: 42 (path 15 -> 20 -> 7).

Giải pháp DFS post-order tối ưu

python

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
 
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            # Cắt bỏ đóng góp âm: subtree tệ đáng giá 0, không phải tổng âm của nó
            left_gain = max(0, dfs(node.left))
            right_gain = max(0, dfs(node.right))
 
            # Node này làm đỉnh của path cong — cập nhật global max
            self.max_sum = max(self.max_sum, node.val + left_gain + right_gain)
 
            # Trả về cánh tay đơn tốt nhất cho cha
            return node.val + max(left_gain, right_gain)
 
        dfs(root)
        return self.max_sum

csharp

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    private int maxSum;
 
    public int MaxPathSum(TreeNode root) {
        maxSum = int.MinValue;
        Dfs(root);
        return maxSum;
    }
 
    private int Dfs(TreeNode node) {
        if (node == null) return 0;
 
        int leftGain = Math.Max(0, Dfs(node.left));
        int rightGain = Math.Max(0, Dfs(node.right));
 
        // Path cong ứng cử qua node này
        maxSum = Math.Max(maxSum, node.val + leftGain + rightGain);
 
        // Chỉ trả về cánh tay đơn tốt nhất lên trên
        return node.val + Math.Max(leftGain, rightGain);
    }
}

Mọi node được thăm đúng một lần. Tại mỗi node, công việc là O(1). Tổng: O(N) time, O(H) space cho call stack.

Tại sao `max(0, ...)` với child gain là an toàn

Đây là move greedy mà mọi người đôi khi băn khoăn. Nếu cánh tay subtree trái tốt nhất là âm, bạn đặt left_gain = 0. Bạn đang giả vờ subtree trái không tồn tại trong phép tính đỉnh. Điều đó đúng vì bao gồm cánh tay âm làm giảm bất kỳ tổng nào một cách nghiêm ngặt — tốt hơn bao giờ cũng là dừng ở node hiện tại hơn là tiếp tục vào subtree kéo tổng xuống.

Định nghĩa path cho phép dừng ở bất kỳ node nào, nên "chỉ node này" là path hợp lệ. max(0, child_gain) là cách viết tắt cho "bao gồm cánh tay con này nếu và chỉ nếu nó có ích."

Các edge case đáng chú ý

Node đơn (root = [5]): dfs được gọi với một lá. Cả left_gain và right_gain đều là 0 (con null trả về 0). Đỉnh = 5. Global max = 5. Trả về cánh tay = 5. Output: 5. Đúng — path duy nhất là node đơn đó.

Toàn bộ giá trị âm (root = [-3, -1, -2]): khởi tạo max_sum = float('-inf') (Python) hoặc int.MinValue (C#) là thiết yếu. Bài toán đảm bảo path không rỗng, nên đáp án phải là giá trị node nào đó, kể cả khi mọi giá trị đều âm. Nếu bạn khởi tạo bằng 0 bạn sẽ trả về 0 cho cây toàn âm — sai. Tại mỗi node, max_gain = max(0, child_gain) nghĩa là các con không đóng góp gì, nên mọi đỉnh = node.val. Global max cuối cùng là giá trị âm nhỏ nhất trong cây.

Path bỏ qua root: Ví dụ 2 ([-10, 9, 20, null, null, 15, 7]) minh họa điều này. Đáp án (42) được ghi nhận khi xử lý node 20, không phải root. Biến global max thu nhận các đáp án xuất hiện ở bất kỳ đâu trong cây.

Chuỗi lệch (độ sâu stack tệ nhất): chuỗi 3 * 10^4 node. Recursion stack đạt độ sâu 3 * 10^4. Giới hạn mặc định của Python là 1000, nên bạn cần sys.setrecursionlimit(40000) trong môi trường thực (judge của LeetCode thường đặt giới hạn cao hơn). C# có stack mặc định lớn hơn nhiều và xử lý tốt.

Path là một cánh tay thẳng: thuật toán xét đỉnh tại mỗi node; nếu đỉnh tốt nhất ở bất kỳ đâu là node chỉ dùng một cánh tay, thì right_gain hoặc left_gain bằng 0 và đỉnh = node.val + one_arm. Công thức path cong tự nhiên suy biến thành cánh tay thẳng.

Approach nào tôi sẽ ship, và tại sao

Tôi sẽ ship DFS single-pass không chút do dự. Phiên bản brute-force chỉ hữu ích như oracle kiểm tra độ đúng đắn — bạn chạy cả hai trên random trees và so sánh output trong quá trình phát triển. Trong production hay phỏng vấn, phiên bản O(N^2) hai pass không mua được gì và có nguy cơ TLE.

Điểm duy nhất cần chú ý trong DFS là global mutable state. Trong Python tôi dùng self.max_sum trên class instance; trong C# tôi dùng field trên Solution. Nếu bạn không thích cách đó, bạn có thể truyền một array độ dài 1 như mutable container, hoặc dùng return tuple — nhưng mọi cách thay thế đều kém readable hơn và không truyền đạt thêm thông tin gì.

Mental model để mang theo: "cái tôi trả về vs cái tôi ghi lại". Hàm trả về giá trị cánh tay (một chiều, hữu ích với cha). Nó ghi lại giá trị đỉnh (path cong, chỉ hữu ích tại node này, không bao giờ gửi lên). Mọi bài toán cây liên quan đến global optimum trên các path không qua root đều dùng phiên bản nào đó của cách tách này.

Bảng so sánh

Approach	Time	Space	Nhận xét
Brute force (tính lại arm mỗi node)	O(N^2)	O(H)	TLE với N lớn, hữu ích làm test oracle
DFS post-order (single pass)	O(N)	O(H)	Ship cái này

Vị trí trong series trees và những bước tiếp theo

Đây là bài thứ 14 trong series trees. Đến đây bạn đã thấy DFS recursion (Maximum Depth, Invert Binary Tree, Same Tree), BFS (Level Order Traversal), và bài toán subtree (Subtree of Another Tree, Validate BST). Điểm mới ở đây là pattern global-max-over-subtree: đáp án nằm tại một node nội bộ nào đó bạn khám phá giữa chừng DFS, không phải tại root. Pattern đó xuất hiện trong nhiều bài cây khó hơn.

Diameter of Binary Tree (543) là sibling gần nhất. Thay "max path sum" bằng "max path length tính theo số cạnh." Cấu trúc giống hệt: tại mỗi node, kết hợp độ sâu trái và phải cho giá trị đỉnh, trả về một độ sâu cho cha. Nếu bài này hiểu được rõ ràng, 543 sẽ cảm thấy như một template.

Longest Univalue Path (687) thêm ràng buộc: path phải gồm các node có cùng giá trị. Quyết định arm-hoặc-zero trở thành "chỉ kéo dài vào con nếu giá trị con bằng giá trị hiện tại." Cùng pattern hai-giá-trị-trả-về, quy tắc mở rộng chặt hơn.

Path Sum III (437) hỏi về số lượng path có tổng bằng target, cho phép path bắt đầu và kết thúc ở bất kỳ đâu. Nó dùng prefix sum với hash map thay vì post-order DP, nên kỹ thuật khác — nhưng setup "path không cần qua root" giống nhau.

Count Good Nodes in Binary Tree (1448) luồng một giá trị "max seen so far" xuống qua DFS theo hướng top-down thay vì bottom-up — một chiều luồng thông tin khác, là điểm đối chiếu hữu ích để nội hóa bên cạnh pattern bottom-up ở đây.

Thuộc series: Trees

BẢN TIN

Đôi dòng ghi chép về những gì tôi đang xây

Nhận email khi tôi đăng bài mới — các bài kỹ thuật, không spam. Hủy đăng ký bất cứ lúc nào.

Bình luận

Chưa có bình luận nào. Hãy là người đầu tiên.

Đăng nhập để tham gia thảo luận