LeetCode_BinaryTree_50. Binary Tree Maximum Path Sum 二叉树中的最大路径和【递归】【Java】【困难】

目录

一，题目描述

英文描述

中文描述

示例与说明

二，解题思路

三，AC代码

Java

四，解题过程

第一搏

第二搏

一，题目描述

英文描述

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

中文描述

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例与说明

提示：

• 树中节点数目范围是 [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

最大路径只有三种情况：（其中最优路径为负时，不纳入结果计算中）

• 左子树中最优路径 + 根节点 + 右子树中最优路径；
• 左子树中最优路径；
• 右子树中最优路径；

设计递归程序时，需要注意自定义方法getMaxPathSum的返回值不需要设置为最终结果（如果设置为最终结果的话，就需要在递归程序中考虑是否采取根节点、是否采取左右子树等细节，最终导致递归程序越来越复杂，没有充分利用递归简化细节的特点）

这里将getMaxPathSum的返回值定义为：root.val + max(maxLeftSum, maxRightSum)，即根节点+左右子树中较大的路径和。（因为只要是一条路径，就一定包含根节点，所以返回的结果中必须要包含根节点的值，这样才不会遗漏）

需要注意一点：

• getMaxPathSum的返回值是包含根节点的最优路径，不一定是最终的结果！！！所以需要在全局设置一个变量，用来存储遍历过程中的最终结果；

三，AC代码

Java

class Solution {private int ans = -1001;public int maxPathSum(TreeNode root) {getMaxPathSum(root);return ans;}public int getMaxPathSum(TreeNode root) {if (root == null) return 0;// 小于零表示会产生负增益，需要剔除int maxLeftSum = Math.max(getMaxPathSum(root.left), 0);int maxRightSum = Math.max(getMaxPathSum(root.right), 0);int tempSum = root.val + maxLeftSum + maxRightSum;// 在递归的过程中获得并更新最大值ans = Math.max(ans, tempSum);return root.val + Math.max(maxLeftSum, maxRightSum);}
}

四，解题过程

第一搏

唉，面向测试用例编程也搞不定。。。

class Solution {public int maxPathSum(TreeNode root) {int[] ans = getMaxPathSum(root, root);return ans[0];}public int[] getMaxPathSum(TreeNode root, TreeNode sourceRoot) {int[] ans = new int[2];ans[0] = -1001;// !!!记得初始化ans[1] = 0;if (root == null) return ans;int[] leftPathSum = getMaxPathSum(root.left, sourceRoot);int[] rightPathSum = getMaxPathSum(root.right, sourceRoot);// 根节点值大于零if (root.val >= 0) {// 左右两子树的根节点都没有被采纳if (leftPathSum[1] == 0 && rightPathSum[1] == 0) {if (root.val >= leftPathSum[0] && root.val >= rightPathSum[0]) {ans[0] = root.val;ans[1] = 1;// 表示将根节点纳入选择的路径中} else {ans[0] = Math.max(leftPathSum[0], rightPathSum[0]);ans[1] = 0;}}// 只有左子树根节点被采纳else if (leftPathSum[1] == 1 && rightPathSum[1] == 0) {// 左子树最优值+根节点值 >= 右子树最优值if (root.val + leftPathSum[0] >= rightPathSum[0]) {ans[0] = root.val + leftPathSum[0];ans[1] = 1;} // 左子树最优值+根节点值 < 右子树最优值else {ans[0] = rightPathSum[0];ans[1] = 0;// 由于右子树根节点没有被采纳，所以这里断开了}}// 只有右子树根节点被采纳else if (rightPathSum[1] == 1 && leftPathSum[1] == 0) {if (root.val + rightPathSum[0] >= leftPathSum[0]) {ans[0] = root.val + rightPathSum[0];ans[1] = 1;} else {ans[0] = leftPathSum[0];ans[1] = 0;}}// 左右两子树的根节点都被采纳else {// 当root节点为为最开始树的根节点时，可以同时采纳左右两子树if (root == sourceRoot) {ans[0] = root.val + leftPathSum[0] + rightPathSum[0];} else {ans[0] = root.val + Math.max(leftPathSum[0], rightPathSum[0]);}ans[1] = 1;}} else {ans[0] = Math.max(leftPathSum[0], rightPathSum[0]);ans[0] = Math.max(ans[0], root.val);}return ans;}
}

第二搏

唉，不知不觉又陷入了递归的细节中，设计递归过程切忌这一点！！！

最大路径只有三种情况：

• 左子树中最优路径 + 根节点 + 右子树中最优路径；
• 左子树中最优路径；
• 右子树中最优路径；

需要注意一点：

• getMaxPathSum的返回值是包含根节点的最优路径，不一定是最终的结果！！！所以需要在全局设置一个变量，用来存储遍历过程中的最终结果；

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！