LeetCode_二叉树_困难_124. 二叉树中的最大路径和
2023-09-27 14:25:46 时间
1.题目
路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点,且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root,返回其最大路径和。
示例 1:
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
提示:
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-tree-maximum-path-sum
2.思路
(1)后序遍历
3.代码实现(Java)
//思路1————后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
oneSideMax(root);
return res;
}
public int oneSideMax(TreeNode root) {
if (root == null) {
return 0;
}
int leftMaxSum = Math.max(0, oneSideMax(root.left));
int rightMaxSum = Math.max(0, oneSideMax(root.right));
//后序遍历位置,顺便更新最大路径和
int pathMaxSum = root.val + leftMaxSum + rightMaxSum;
res = Math.max(pathMaxSum, res);
/*
实现函数定义,左右子树的最大单边路径和加上当前根节点的值
就是从当前根节点 root 为起点的最大单边路径和
*/
return Math.max(leftMaxSum, rightMaxSum) + root.val;
}
}
相关文章
- 【LeetCode】二叉树展开为链表 [M](Morris遍历)
- 【LeetCode】从前序与中序遍历序列构造二叉树 [M](二叉树重构)
- LeetCode_二叉平衡树_简单_110.平衡二叉树
- LeetCode_栈_中等_921.使括号有效的最少添加
- LeetCode_二叉树_前缀和_中等_437.路径总和 III
- LeetCode_拓扑排序_BFS_中等_210.课程表 II
- LeetCode_二叉树_BFS_中等_103. 二叉树的锯齿形层序遍历
- LeetCode_回溯算法_动态规划_简单_104.二叉树的最大深度
- LeetCode·124.二叉树中的最大路径和·递归
- LeetCode·每日一题·623.在二叉树中增加一行·递归·迭代
- 【LeetCode从零单排】No104 Maximum Depth of Binary Tree
- [LeetCode] 741. Cherry Pickup 捡樱桃
- [LeetCode] 366. Find Leaves of Binary Tree 找二叉树的叶节点
- [LeetCode] 267. Palindrome Permutation II 回文全排列 II
- [LeetCode] 31. Next Permutation 下一个排列
- leetcode 257 二叉树的所有路径
- leetcode 104 二叉树的最大深度