題目網址：https://leetcode.cn/problems/binary-tree-maximum-path-sum/

題意：給一 BT 的 root, 返回其最大的 path sum。

path 定義：為一條從 tree 中任意 node 出發, 最後抵達任意 node 的 sequence。同一個 node 在一條 path 中至多出現一次。該 path 至少包含一個 node, 且不一定經過 root。

Solution：

想法：利用 DFS, 類似 543. Diameter of Binary Tree, dfs(node) 返回以 node 為 root 之 subtree 中 path sum 之最大值, 只有當前 node 可以同時使用左子樹和右子樹, 也就是計算 res 時可同時用左子樹和右子樹, 但返回時只能 return 單邊路徑。由於 path 不一定要經過 root, 因此可用 global 變數 res 來記錄最大 path sum

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = root->val;
        dfs(root, res);
        return res;
    }

private:
    int dfs(TreeNode* root, int& res){
        if (!root) {
            return 0;
        }

        int left = dfs(root->left, res);
        int right = dfs(root->right, res);
        left = max(left, 0); // 如果 left < 0, 則不取
        right = max(right, 0); // 如果 right < 0, 則不取
        res = max(res, root->val + left + right); // 當前 root 可同時使用左、右子樹

        return root->val + max(left, right); // 只能返回單邊路徑和
    }
};
  • time：$O(n)$ ➔ 遍歷 BT
  • space：$O(n)$ ➔ 取決於遞迴深度, worse case：skew tree