佳能网站建设需求报告,上海人才服务网官网,免费咨询中心,县建设局 协会网站题目
在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点#xff0c;不一定经过二叉树的根节点#xff0c;也不一定经过叶节点。给定非空的一棵二叉树#xff0c;请求出二叉树所有路径上节点值之和的最…题目
在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点不一定经过二叉树的根节点也不一定经过叶节点。给定非空的一棵二叉树请求出二叉树所有路径上节点值之和的最大值。例如在如图8.6所示的二叉树中从节点15开始经过节点20到达节点7的路径的节点值之和为42是节点值之和最大的路径。
分析
这个题目中二叉树路径的定义又和前面的不同。这里的路径最主要的特点是路径有可能同时经过一个节点的左右子节点。例如在图8.6中一条路径可以经过节点15、节点20和节点7即节点20的左子节点15和右子节点7同时在一条路径上。当然路径也可以不同时经过一个节点的左右子节点。例如在图8.6中一条路径可以经过节点-9、节点20、节点15和节点-3。
也就是说当路径到达某个节点时该路径既可以前往它的左子树也可以前往它的右子树。但如果路径同时经过它的左右子树那么就不能经过它的父节点。
由于路径可能只经过左子树或右子树而不经过根节点为了求得二叉树的路径上节点值之和的最大值需要先求出左右子树中路径节点值之和的最大值左右子树中的路径不经过当前节点再求出经过根节点的路径节点值之和的最大值最后对三者进行比较得到最大值。由于需要先求出左右子树的路径节点值之和的最大值再求根节点这看起来就是后序遍历。
解
public class Test {public static void main(String[] args) {TreeNode node_9 new TreeNode(-9);TreeNode node4 new TreeNode(4);TreeNode node20 new TreeNode(20);TreeNode node15 new TreeNode(15);TreeNode node7 new TreeNode(7);TreeNode node_3 new TreeNode(-3);node_9.left node4;node_9.right node20;node20.left node15;node20.right node7;node15.left node_3;int result maxPathSum(node_9);System.out.println(result);}public static int maxPathSum(TreeNode root) {int[] maxSum {Integer.MIN_VALUE};dfs(root, maxSum);return maxSum[0];}private static int dfs(TreeNode root, int[] maxSum) {if (root null) {return 0;}int[] maxSumLeft {Integer.MIN_VALUE};int left Math.max(0, dfs(root.left, maxSumLeft));int[] maxSumRight {Integer.MIN_VALUE};int right Math.max(0, dfs(root.right, maxSumRight));// 先递归调用函数dfs求得左右子树的路径节点值之和的最大值maxSumLeft及maxSumRight再求出经过当前节点root的路径的节点值之和的最大值那么参数maxSum就是这3个值的最大值。maxSum[0] Math.max(maxSumLeft[0], maxSumRight[0]);maxSum[0] Math.max(maxSum[0], root.val left right);// 先left代表左树right代表右树return root.val Math.max(left, right);// 后是子树的行为不是本身这个节点的行为}
}
