本题需要比较以下四种情况的值
1、 root节点本身的值
2、root和左子树的值
3、root和右边子树的值
4、root和左右子树的值
需要注意的是，第四种情况下，root的左右节点中只选取一条路径，不能跨国左右子树的节点，这是因为选一条路径
需要在局部维护一个sum变量，全局维护一个maxSum变量。一旦在递归中计算的子树发现比maxSum大的时候，就用sum去更新maxSum节点。这样可以有效求出来究竟是子树的值较大还是横跨根节点的值更大
在每一层中，如果左右子树的节点值为正整数，就加上左子树和右子树的值。之后进入比较，查看是否有更新，如果没有，返回maxSum作为当前根节点的子树的最大值得路径
代码实现核心如下：
代码截图
可以看到，当且仅当左右子树大于0的时候，才会返回加和，否则只使用root的值作为返回
LeetCode-124-二叉树中的最大路径和 124. 二叉树中的最大路径和[https://leetcode-...
leetcode 124 二叉树的最大路径和 例：10/ \-1 20最大的路径和为 30,。这...
一 题目描述 124. 二叉树中的最大路径和 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树...
一 题目描述 124. 二叉树中的最大路径和 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树...
概述 前言 104 二叉树的最大深度【简单】 111 二叉树的最小深度 【简单】 124 二叉树中的最大路径和 【...
hard Question 寻找二叉树的最大路径和，路径可以起始和终止与树的任意节点，可以不经过根节点。假设二叉树...
二叉树中的最大路径和 描述 给定一个非空二叉树，返回其最大路径和。 解题思路 1、对每一个节点都计算出有穿过它但不...
二叉树的最大深度与最小深度 二叉树的最大深度 最大深度是指二叉树根节点到该树叶子节点的最大路径长度。而最小深度自然...
本题需要比较以下四种情况的值 1、 root节点本身的值 2、root和左子树的值 3、root和右边子树的值 4...
描述 给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的...
本文标题：2019-06-14 二叉树的最大路径和
本文链接：https://www.haomeiwen.com/subject/zrhpfctx.html
网友评论