leetcode-124-二叉树中的最大路径和-java

  • 时间:
  • 来源:互联网

题目及测试

package pid124;


/*二叉树中的最大路径和

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

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42


}*/
public class main {
	
	public static void main(String[] args) {
		Object[] x=new Object[]{-10,9,20,null,null,15,7};	
		BinaryTree tree=new BinaryTree(x);
		tree.printTree(tree.root);
		test(tree.root);
		
		
	}
		 
	private static void test(TreeNode ito) {
		Solution solution = new Solution();
		int rtn;
		long begin = System.currentTimeMillis();
		rtn = solution.maxPathSum(ito);//执行程序
		long end = System.currentTimeMillis();		
		System.out.println("rtn=" );
		System.out.print(rtn);
		System.out.println();
		System.out.println("耗时:" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

没想出来

解法1(别人的)

初始化 max_sum 为最小可能的整数并调用函数 max_gain(node = root)。

实现 max_gain(node) 检查是继续旧路径还是开始新路径:

边界情况:如果节点为空,那么最大权值是 0 。
对该节点的所有孩子递归调用 max_gain,计算从左右子树的最大权值:left_gain = max(max_gain(node.left), 0) 和 right_gain = max(max_gain(node.right), 0)。
检查是维护旧路径还是创建新路径。创建新路径的权值是:price_newpath = node.val + left_gain + right_gain,当新路径更好的时候更新 max_sum。
对于递归返回的到当前节点的一条最大路径,计算结果为:node.val + max(left_gain, right_gain)。

即max_gain(node)方法,会返回node节点-它的某一侧的节点的最大长度。

某一侧节点-node-另一侧节点,这种情况的路径,会在方法内部更新max_sum字段,更新最大长度。

class Solution {
  int max_sum = Integer.MIN_VALUE;

  public int max_gain(TreeNode node) {
    if (node == null) return 0;

    // max sum on the left and right sub-trees of node
    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);

    // the price to start a new path where `node` is a highest node
    int price_newpath = node.val + left_gain + right_gain;

    // update max_sum if it's better to start a new path
    max_sum = Math.max(max_sum, price_newpath);

    // for recursion :
    // return the max gain if continue the same path
    return node.val + Math.max(left_gain, right_gain);
  }

  public int maxPathSum(TreeNode root) {
    max_gain(root);
    return max_sum;
  }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

xushiyu1996818
发布了438 篇原创文章 · 获赞 62 · 访问量 10万+

本文链接http://element-ui.cn/news/show-999.aspx