124. Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

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

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Thoughts

二叉树上返回和最大的路径和。和diameter异曲同工。分治，global max记录全局最优, helper返回从下往上且包含当前节点的能继续往上延伸的最大sum。全局最优可能是同时包含左右两支。由于负数的存在，返回时node.val+max(l, r, 0)，表示局部最优是负数时最佳选择是不选子结点。

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = -float(inf)
    
    def dfs(self, node):
        if node == None:
            return 0
        l, r = self.dfs(node.left), self.dfs(node.right)
        self.res = max(self.res, node.val + max(l, 0) + max(r, 0))
        return node.val + max(0, max(l, r))
        
    def maxPathSum(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res

Analysis

每个节点遍历一次, 时间复杂度O(N).

Ver.2

用区分backtracking的Iterative写。 当pop()后, peek()得到的是pop的父节点.和分治一样直接利用pop()时对应的preRes. 如果还有右子树没处理, 则不pop父节点, 而同样处理右子树. 注意这时preRes需要清零, 因为preRes存的还是左子树的结果, 右子树肯定不能直接用到左子树的结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        stack<TreeNode*> s;
        stack<int> mlens;
        TreeNode *pre;
        int plen = 0;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != NULL) {
                s.push(cur);
                mlens.push(0);
                cur = cur->left;
            }
            pre = NULL;
            plen = 0;
        };
        push_left(root);
        while (!s.empty()) {
            const auto cur = s.top();
            auto &mlen = mlens.top();
            if (cur->right != pre) {
                // Handling left backtracking.
                mlen = plen;
                push_left(cur->right);
                continue;
            }
            // Handling right backtracking.
            int l = max(0, mlen);
            int r = max(0, plen);
            res = max(res, cur->val + l + r);
            plen = cur->val + max(l, r);
            pre = cur;
            s.pop();
            mlens.pop();
        }
        
        return res;
    }
};