LeetCode Binary Tree Maximum Path Sum 解题报告

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.

For example:
Given the below binary tree,
       1
      /  \

     2    3

Return 6.

http://oj.leetcode.com/problems/binary-tree-maximum-path-sum/

解题报告: 返回树中任意两点路径的最大值。只要两点间有路径联通就可以。
初步一看使用递归,但一直WA。后来发现,没有分清最大值和递归函数的返回值。
在求值函数里面不能把计算出来的最大值作为返回值返回回去,否则会有问题。

例如对于下面的这个树:

     1
   /     \

1         -3

         / 

      3

计算到-3节点时,它求出的maxSum(root.left)是3,可以用3更新max,但不能把3作为1的maxSum(root.right)返回给节点1。
如果返回给1的话,会算出最大值为4。
-3节点实际返回给1的是0。

上AC代码:

public class Solution {    int max = Integer.MIN_VALUE;        public int maxSum(TreeNode root) {        if(root==null) {            return 0;        }                int  value  = root.val;        int  lmax = 0;        int  rmax = 0;        if(root.left!=null) {            lmax = maxSum(root.left);            if(lmax>0) {            	value  += lmax;            }        }                if(root.right!=null) {            rmax = maxSum(root.right);            if(rmax>0) {            	value  += rmax;            }        }        //更新最大值        //max is the max of {root.val,root.val+lmax,root.val+rmax, root.val + lmax + rmax}        if (value>max) {        	max = value;        }        //返回值        //return max of (root.val, root.val + lmax, root.val + rmax)        return  Math.max(root.val,Math.max(root.val + lmax, root.val + rmax));    }        public int maxPathSum(TreeNode root) {        if(root==null) {            return 0;        }        maxSum(root);        return max;    }}

点这里可以跳转到人工智能网站