题目描述

给定一个非空二叉树，返回其最大路径和。
blablabla

样例

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

算法1 $O(n)$

C++ 代码

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int sum = INT_MIN;
        maxPathSum(root, sum);
        return sum;
    }
private:
    int maxPathSum(TreeNode* node, int& sum) {
        if (!node) {
            return 0;
        }
        int left = max(0, maxPathSum(node -> left, sum));
        int right = max(0, maxPathSum(node -> right, sum));
        sum = max(sum, left + node -> val + right);
        return max(left, right) + node -> val;
    }
};

算法2

(Recursion递归) $O(n)$

时间复杂度

参考文献

Python 代码

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        max_path = float("-inf") # placeholder to be updated
        def get_max_gain(node):
            nonlocal max_path # This tells that max_path is not a local variable
            if node is None:
                return 0
            gain_on_left = max(get_max_gain(node.left), 0) # Read the part important observations
            gain_on_right = max(get_max_gain(node.right), 0)  # Read the part important observations

            current_max_path = node.val + gain_on_left + gain_on_right # Read first three images of going down the recursion stack
            max_path = max(max_path, current_max_path) # Read first three images of going down the recursion stack
            return node.val + max(gain_on_left, gain_on_right) # Read the last image of going down the recursion stack
        get_max_gain(root) # Starts the recursion chain
        return max_path