可做长图的网站,网站后台怎么用ftp打开,手机版免费个人简历,网站安全风险提示单文章目录题目描述思路 代码更新版题目描述
好家伙我可太激动了#xff0c;第一次光速A困难题。应该是因为写过类似的二叉树的直径#xff0c;不过这道倒是属于简单题。。面试常考题#xff0c;刷codetop看到了就写写
思路 代码
递归过程是自底向上的递归过程…
文章目录题目描述思路 代码更新版题目描述
好家伙我可太激动了第一次光速A困难题。应该是因为写过类似的二叉树的直径不过这道倒是属于简单题。。面试常考题刷codetop看到了就写写
思路 代码
递归过程是自底向上的递归过程求出当前最大值 ans维护 max 用于返回答案递归过程求出当前还可继续走的最大路径 forPa用于父结点继续使用时间复杂度 O(n)相当于每个结点走了一趟
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {// 在递归过程中维护一个需要返回的 max 值int max Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {forMax(root);return max;}int forMax(TreeNode root){if(root null){return Integer.MIN_VALUE;}// 先往左右子结点走int left forMax(root.left);int right forMax(root.right);// ans用于维护 max可能已经不能往上走了已经走了左右子树int ans root.val;// 不一定取因为可能是负数ans left 0 ? left : 0;ans right 0 ? right : 0;max Math.max(ans, max);// forPa用于给上层结点一定不是同时走了左右子树的路径int forPa root.val;// 最多只能走一边走左 or 右 or 不走int add left right ? left : right;if(add 0){forPa add;}// 返回往上走的可行路径最大值return forPa;}
}更新版
照例感叹之前写的代码怎么这么冗余。。
class Solution {int max Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxPath(root);return max;}public int maxPath(TreeNode root) {if(root null) {return 0;}int left Math.max(0, maxPath(root.left));int right Math.max(0, maxPath(root.right));max Math.max(root.val left right, max);return Math.max(left root.val, right root.val);}
}
