題目： LeetCode - 124. Binary Tree Maximum Path Sum

題目說明

給一個 Binary Tree，求最大路徑和。

解題思路

使用遞迴即可。核心觀念為：最大路徑和有沒有包含 root ( 自己 )？

  • 若有：最大路徑和為：左邊的最大路徑和 ( 需包含 root，但可以不選) + root->val + 右邊的最大路徑和 ( 需包含 root，但可以不選)。
  • 若沒有：最大路徑和為：左邊的最大路徑和 ( 任意起點任意終點 ) 及 右邊的最大路徑和 ( 任意起點任意終點 ) 兩者取其大。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    // 找出以 root 為起點的最大路徑和
    int maxPath(TreeNode* root)
    {
        if(!root)
            return 0;
        return max(maxPath(root->left) + root->val, max(maxPath(root->right) + root->val, 0));
    }
    // 找出任意起點任意終點的最大路徑和
    int maxPathSum(TreeNode* root) {
       if(!root) 
           return INT_MIN;
        return max(maxPathSum(root->left), max(maxPath(root->left) + root->val + maxPath(root->right), maxPathSum(root->right)));
    }
};