企业官网建设流程全解析

最便宜的外贸网站建设,网站支持ipv6怎么做,wordpress首页文章图片不显示,公司部门二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root #xff0c;返回…二叉树中的路径被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点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关键点设置全局变量记录最大值递归调用在递归里做两件事递归计算左右子节点的最大贡献值根据返回的最大贡献值返回当前节点和左/右节点(谁大取谁, 如果都小于0则取0)的和记为当前节点的最大贡献值计算出一个最大路径和根节点左最大贡献值右最大贡献值和全局最大路径取大者Integer maxSum Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode root) { if (root null) { return 0; } // 递归计算左右子节点的最大贡献值 只有在最大贡献值大于0时才会选取对应子节点 int leftGain Math.max(maxGain(root.left), 0); int rightGain Math.max(maxGain(root.right), 0); // 计算新的最大贡献值 根节点左子节点的最大贡献值右子节点的最大贡献值 int newSum root.val leftGain rightGain; // 和全局最大贡献值取大者 maxSum Math.max(maxSum, newSum); // 返回节点的最大贡献值 return root.val Math.max(leftGain, rightGain); }