Leetcode: Binary Tree Maximum Path Sum
LeetCode Tree path Binary sum maximum
2023-09-11 14:14:08 时间
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6.
难度:75.
参见了他人的思路,这道题是求树的路径和的题目,不过和平常不同的是这里的路径不仅可以从根到某一个结点,而且路径可以从左子树某一个结点,然后到达右子树的结点,就像题目中所说的可以起始和终结于任何结点。函数的返回值定义为以自己为根的一条从根到叶子结点的最长路径,这个返回值是为了提供给它的父结点计算自身的最长路径用。这样一来,一个结点自身的最长路径就是它的左子树返回值(如果大于0的话),加上右子树的返回值(如果大于0的话),再加上自己的值。在过程中求得当前最长路径时比较一下是不是目前最长的,如果是则更新。算法的本质还是一次树的遍历,所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。注意这里path的存值方式是个问题,如果用一个integer变量代入recursion的话,函数无法对实参造成改变,所以用了一个对象ArrayList<Integer> res的第一个元素来存最大的path值
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public int maxPathSum(TreeNode root) { 12 if (root == null) return 0; 13 ArrayList<Integer> res = new ArrayList<Integer>(); 14 res.add(Integer.MIN_VALUE); 15 FindMaxSum(root, res); 16 return res.get(0); 17 } 18 19 public int FindMaxSum(TreeNode root, ArrayList<Integer> res) { 20 if (root == null) { 21 return 0; 22 } 23 int leftsum = FindMaxSum(root.left, res); 24 int rightsum = FindMaxSum(root.right, res); 25 int maxsum = root.val + (leftsum>0? leftsum : 0) + (rightsum>0? rightsum : 0); 26 if (maxsum > res.get(0)) res.set(0, maxsum); 27 return root.val + Math.max(leftsum, Math.max(rightsum, 0)); 28 } 29 }
Or we can use external variable
1 class Solution { 2 int maxSum = Integer.MIN_VALUE; 3 public int maxPathSum(TreeNode root) { 4 helper(root); 5 return maxSum; 6 } 7 8 public int helper(TreeNode node) { 9 if (node == null) return 0; 10 int left = helper(node.left); 11 int right = helper(node.right); 12 maxSum = Math.max(maxSum, node.val + (left > 0 ? left : 0) + (right > 0 ? right : 0)); 13 return node.val + Math.max(0, Math.max(left, right)); 14 } 15 }
相关文章
- Leetcode: Verify Preorder Serialization of a Binary Tree
- Leetcode: Binary Tree Upside Down
- Leetcode: Recover Binary Search Tree
- Leetcode: Letter Combinations of a Phone Number
- Leetcode: Minimum Depth of Binary Tree
- Leetcode: Balanced Binary Tree
- [LeetCode] Validate Binary Search Tree
- [LeetCode]1295. 统计位数为偶数的数字
- 85、【栈与队列】leetcode ——150. 逆波兰表达式求值(C++版本)
- 2404. 出现最频繁的偶数元素(leetcode)
- 【LeetCode】52. N-Queens II
- 【LeetCode】94. Binary Tree Inorder Traversal (3 solutions)
- 【LeetCode】100. Same Tree (2 solutions)
- 【LeetCode】105. Construct Binary Tree from Preorder and Inorder Traversal
- 【LeetCode】145. Binary Tree Postorder Traversal (3 solutions)
- 【LeetCode】51. N-Queens
- LeetCode_Maximum Depth of Binary Tree
- [LeetCode] 1299. Replace Elements with Greatest Element on Right Side 将每个元素替换为右侧最大元素
- [LeetCode] 1290. Convert Binary Number in a Linked List to Integer 二进制链表转整数
- [LeetCode] 1104. Path In Zigzag Labelled Binary Tree 之字形二叉树路径
- [LeetCode] 1161. Maximum Level Sum of a Binary Tree 最大层内元素和
- [LeetCode] 1145. Binary Tree Coloring Game 二叉树着色游戏
- [LeetCode] 827. Making A Large Island 建造一个巨大岛屿
- [LeetCode] 660. Remove 9 移除9
- [LeetCode] Subtree of Another Tree 另一个树的子树
- [LeetCode] 254. Factor Combinations 因子组合
- [LeetCode] 227. Basic Calculator II 基本计算器之二
- [LeetCode] 52. N-Queens II N皇后问题之二
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
- leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal 根据前序和后
- leetcode 572. Subtree of Another Tree 另一棵树的子树 (简单)