Problem: 124. 二叉树中的最大路径和
文章目录
- 解题方法
- 复杂度
- 💖 Code
解题方法
👨🏫 参考思路
复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
💖 Code
/*** 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 {int ans = -20000;//此处的最小值一定要小于数据范围的最小值 -10000public int maxPathSum(TreeNode root){cal(root);return ans;}/*** @param root 当前树的节点* @return 当前树的单侧最大路径长度*/private int cal(TreeNode root){if (root == null)// 访问到叶子节点,返回 0return 0;int l = cal(root.left);// 递归计算左右子树int r = cal(root.right);int max = l > r ? l : r;// 记录左臂右膀的长度int t = root.val;// t 记录的是以当前 root 为转折点的路径长度if (l > 0)// 负数则舍弃t += l;if (r > 0)t += r;int res = root.val;// res = 左右子树单侧路径较长者 + 当前root的值if (max > 0)// 同理,不要负值拖油瓶res += max;ans = Math.max(ans, t);// 更新全局答案return res;}
}