Binary Tree Maximum Path Sum

迷南。 2021-12-17 10:35 172阅读 0赞

Given a 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 does not need to go through the root.

For example:  
Given the below binary tree,

1
          / \
         2   3

Return `6`.

这是一道二叉树递归的终极版本，需要求二叉树中从任意结点到任意结点的最长路径。与[Path Sum II][](从root到leaf的路径）相比，这道题更tricky。

使用分治思路devide and conquer来解这道题，求以某个结点（node)为根的any to any最大路径，可以分解为： 1.经过该结点的路径中的最大值(如2-->1-->3)（注意如果node.left,node.right的root2any都为负就只取node.val)；2.该结点左子树中any to any的最大路径, 如举例中的2；3该结点右子树中any to any 的最大路径，如举例中的3。

但是每次第1种路径需要用到以结点左孩子(node.left)为结尾的最大路径(可以翻转过来依然以node.left为起点朝下走的路径）和以结点右孩子(node.right)为起点朝下走的最大路径和。一个简单的思路是每个子问题都返回以node为起点的 root to any的和 node为根的树中的 any to any。前者是为了辅助计算，后者是为了得到最终的结果。这种代码的最终实现Java版为：

public class Solution {
        /**
         * @param root: The root of binary tree.
         * @return: An integer.
         */
        private class ResultType {
            int root2Any, any2Any;
            ResultType(int root2Any, int any2Any) {
                this.root2Any = root2Any;
                this.any2Any = any2Any;
            }
        }
    
        private ResultType helper(TreeNode root) {
            if (root == null) {
                return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE); //两种路径中都最少包括一个结点
            }
            // Divide
            ResultType left = helper(root.left);
            ResultType right = helper(root.right);
    
            // Conquer
            int root2Any =
                Math.max(0, Math.max(left.root2Any, right.root2Any)) + root.val;
    
            int any2Any = Math.max(left.any2Any, right.any2Any);
            any2Any = Math.max(maxPath,
                               Math.max(left.root2Any, 0) + 
                               Math.max(right.root2Any, 0) + root.val);
    
            return new ResultType(root2Any,any2Any );
        }
    
        public int maxPathSum(TreeNode root) {
            ResultType result = helper(root);
            return result.any2Any;
        }
    
    }

但是思考下上面的代码就可以发现，其实并不需要保存每个结点的any2any.可以维护一个当前的最大值，一旦某个node的any2any比目前的any2any大，就更新它，最后返回这个值就可以。也就是helper函数每次只需要返回以输入的结点为根的root2any就可以了，具体代码如下：

对于树的跟节点，需要考虑两种情况，它的产生最大和的路径包含两种可能：1:包含该节点的路径： a.横跨左子树，根节点和右子树。b.左子树的一段，以根节点为结尾。c.右子树的一段，以根节点为结尾。2.左子树或右子树中的一段路径，不包含该节点。 要完成这两点，需要子节点返回：1.以子节点为终点的最大路径和。2.子节点为根的子树中的最大值。考虑到该题需要返回的是全局的最大路径和，可以直接将子树中的最大路径和更新到系统里。

class Solution(object):
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """

res = [-sys.maxint-1]
            self.helper(root,res)
            return res[0]
        def helper(self,node,res):
            if not node:  #don't need to include a node
                return 0
            left = self.helper(node.left,res)   #the max path sum from left node(must include left node)
            right = self.helper(node.right,res) #the max path sum from right node(must include right node)
            
            nodepath = max(max(left,right,0)+node.val #the max path sum from  node(must include the node)
            
            maxpath =  max(left,0)+max(right,0)+node.val   #the max path that cross the node (but not start from, any to any)  
            res[0] = max(res[0],maxpath)
            
            return nodepath

转载于:https://www.cnblogs.com/sherylwang/p/5499595.html

[Path Sum II]: http://www.cnblogs.com/sherylwang/p/5466990.html