dedecms 音乐网站模板,外贸网站建设广州,电商专业培训网站建设,北京网站建设 招聘信息二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根…二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
示例1 输入root [1,2,3] 输出6 解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6
解题思路
这个问题可以使用递归解决对于每个节点
1、以该节点为根的路径和该路径和包括该节点可能往左、往右、或者左右都有。2、以该节点的左子树为起点的最大路径和。3、以该节点的右子树为起点的最大路径和。4、取这三者的最大值作为以当前节点为根的最大路径和。
Java实现
public class MaxPathSum {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}}private int maxSum Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxPathSumHelper(root);return maxSum;}private int maxPathSumHelper(TreeNode node) {if (node null) {return 0;}
// 10
// / \
// 2 10
// / \ \
// 20 1 -25
// / \
// 3 4// 计算以当前节点为根的路径和可能包括左右子树int leftSum Math.max(0, maxPathSumHelper(node.left));int rightSum Math.max(0, maxPathSumHelper(node.right));// 更新全局最大路径和maxSum Math.max(maxSum, leftSum rightSum node.val);// 返回以当前节点为根的路径和的最大值注意不要包括左右子树return Math.max(leftSum, rightSum) node.val;}// 示例测试public static void main(String[] args) {MaxPathSum solution new MaxPathSum();// 构造二叉树TreeNode root new TreeNode(10);root.left new TreeNode(2);root.right new TreeNode(10);root.left.left new TreeNode(20);root.left.right new TreeNode(1);root.right.right new TreeNode(-25);root.right.right.left new TreeNode(3);root.right.right.right new TreeNode(4);int result solution.maxPathSum(root);System.out.println(result); // 输出 42}
}
时间空间复杂度 时间复杂度O(N)其中 N 是二叉树中节点的数量因为我们需要遍历每个节点。 空间复杂度O(H)其中 H 是二叉树的高度因为递归调用栈的深度取决于二叉树的高度。
