[leetcode]Binary Tree Maximum Path Sum

新博文地址:[leetcode]Binary Tree Maximum Path Sum

 

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.

 这道题是非常好的一道题，树，常规做法是遍历，遍历的做法往往用dfs，代码简单，可读性强。这道题与常规的树的题目不同的一点是，在遍历的过程中，进行了返回处理，而且做法很巧妙。

 

以这棵树为例：

                      2
                   /       \
                1         -1
              /     \     /     \
            1     -3  1       7

 图中红色路径表示的一条最大路径：

先看下递归过程：

以左下角的1为root的树的最大路径肯定是1，而异-3为root的树的最大路径是-3，以他俩的父节点1为根节点的最大路径有这么几种情况：

root.val,  root.val + left , root.val + right ,root.val + left + right

取其中的最大值（图中的例子是root.val + left：2），更新max（上面取四个值得最大值，仅用于更新max）

 

但是这个递归函数的返回不应该包括root.val + left + right，因为黄底色的1作为2的左子树的返回值只能由其他节点经过黄底色的1，传到根节点2，单向，传到2，不能形成折路（谁想到的？太厉害了）

 

好了有了以上的算法思想，代码实现起来就比较容易了：

int max = Integer.MIN_VALUE;
	public int maxPathSum(TreeNode root){
		if(root == null) return 0;
		dfs(root);
		return max;		
	}
	public int dfs(TreeNode root){
		if(root == null) return 0;
		int left = dfs(root.left);
		int right = dfs(root.right);
		int tem = Math.max(root.val, Math.max(left+ root.val, Math.max(right + root.val, root.val + left+ right)));
		max = tem > max ? tem : max;
		return Math.max(root.val, Math.max(root.val + left, root.val + right));
	}