首页 > 代码库 > LeetCode: Binary Tree Maximum Path Sum 解题报告

LeetCode: Binary Tree Maximum Path Sum 解题报告

2024-08-08 19:13:57   220人阅读

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

SOLUTION 1:

计算树的最长path有2种情况：

1. 通过根的path.

  (1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

  (2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

 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     public class ReturnType {12         int maxSingle;13         int max;14         ReturnType (int maxSingle, int max) {15             this.max = max;16             this.maxSingle = maxSingle;17         }18     }19     20     public int maxPathSum(TreeNode root) {21         return dfs(root).max;        22     }23     24     public ReturnType dfs(TreeNode root) {25         ReturnType ret = new ReturnType(Integer.MIN_VALUE, Integer.MIN_VALUE);26         if (root == null) {27             return ret;28         }29         30         ReturnType left = dfs(root.left);31         ReturnType right = dfs(root.right);32         33         int cross = root.val;34         35         // if any of the path of left and right is below 0, don‘t add it.36         cross += Math.max(0, left.maxSingle);37         cross += Math.max(0, right.maxSingle);38         39         // 注意，这里不可以把Math.max(left.maxSingle, right.maxSingle) 与root.val加起来，40         // 会有可能越界！41         int maxSingle = Math.max(left.maxSingle, right.maxSingle);42         43         // may left.maxSingle and right.maxSingle are below 044         maxSingle = Math.max(maxSingle, 0);45         maxSingle += root.val;46         47         ret.maxSingle = maxSingle;48         ret.max = Math.max(right.max, left.max);49         ret.max = Math.max(ret.max, cross);50         51         return ret;52     }53 }
View Code

 

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/MaxPathSum.java

LeetCode: Binary Tree Maximum Path Sum 解题报告


联系
我们