首页 > 代码库 > 【leetcode】Binary Tree Maximum Path Sum

【leetcode】Binary Tree Maximum Path Sum

2024-07-11 16:37:16   223人阅读

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.

 

题解：递归的思想，首先要明确一个点root为根的树中路径的最大值有四种情况：

  1. 只有根节点的路径；
  2. 从左子树值最大的路径->根节点；
  3. 从右子树值最大的路径->根节点；
  4. 从左子树值最大的路径->根节点->右子树值最大的路径；

要注意的一点就是递归函数返回的并不是最终的答案。如下图所示：

计算根节点root的最大值，调用递归函数计算左子树的最大路径值是3，如果直接把这个值返回就错了，因为root不通过它的左子-2就不能到达3，所以返回的值应该为经过root并以root为重点的路径的最大值，即root.val+max(left_max,right_max)；而真正的最大值用一个类变量maxx记录，在递归的过程中，这个值随时被更改并保持最大，它等于上述四种情况中最大的一种，在得到left_max和right_max的时候我就直接把它们和0比较取大的，所以不用单独考虑情况2，3了：

maxx =  Math.max(maxx,Math.max(root.val, root.val+left_max+right_max));

一个完整的例子如下图所示，其中花括号中第一个数为递归在该节点上返回的函数值，第二个数为当前maxx的值

代码如下：

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11       private int maxx;12       public int maxPathSum(TreeNode root) {13           if(root == null)14             return 0;15           maxx = root.val;16           Recur(root);17           return maxx;18       }19       20       public int Recur(TreeNode root){21           if(root == null)22               return 0;23               24           int left_max = Recur(root.left);25           left_max = left_max > 0? left_max:0;26           int right_max = Recur(root.right);27           right_max = right_max > 0? right_max:0;28           29           maxx =  Math.max(maxx,Math.max(root.val, root.val+left_max+right_max));30           return root.val+Math.max(left_max,right_max);31       }32 }

代码中第29行更行maxx；

30行返回从左子树（右子树）到根节点的路径最大值


联系
我们