。

路径中至少包含一个节点#xff0c;不一定经过二叉树的根节点#xff0c;也不一定经过叶节点。

给定非空的一棵二叉树#xff0c;请求出二叉树所有路径上节点值之和的最…题目

在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。

路径中至少包含一个节点不一定经过二叉树的根节点也不一定经过叶节点。

给定非空的一棵二叉树请求出二叉树所有路径上节点值之和的最大值。

例如在如图8.6所示的二叉树中从节点15开始经过节点20到达节点7的路径的节点值之和为42是节点值之和最大的路径。

这个题目中二叉树路径的定义又和前面的不同。

这里的路径最主要的特点是路径有可能同时经过一个节点的左右子节点。

例如在图8.6中一条路径可以经过节点15、节点20和节点7即节点20的左子节点15和右子节点7同时在一条路径上。

当然路径也可以不同时经过一个节点的左右子节点。

例如在图8.6中一条路径可以经过节点-9、节点20、节点15和节点-3。

也就是说当路径到达某个节点时该路径既可以前往它的左子树也可以前往它的右子树。

但如果路径同时经过它的左右子树那么就不能经过它的父节点。

由于路径可能只经过左子树或右子树而不经过根节点为了求得二叉树的路径上节点值之和的最大值需要先求出左右子树中路径节点值之和的最大值左右子树中的路径不经过当前节点再求出经过根节点的路径节点值之和的最大值最后对三者进行比较得到最大值。

由于需要先求出左右子树的路径节点值之和的最大值再求根节点这看起来就是后序遍历。

public

maxPathSum(node_9);System.out.println(result);}public

static

先递归调用函数dfs求得左右子树的路径节点值之和的最大值maxSumLeft及maxSumRight再求出经过当前节点root的路径的节点值之和的最大值那么参数maxSum就是这3个值的最大值。

maxSum[0]

Math.max(maxSum[0],