Doordash MLE 跪经

树的题目：叶子结点有asterisk的也有非asterisk的，找到两个asterisk 结点之间最大的path sum。例子

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

刷题，有好的solution建议嘛？希望下次还能碰到～

Super easy solution using Python (please add rice if you like it !!!)

1. class TreeNode(object):
   
2.     def __init__(self, val=0, left=None, right=None, isAsterisk=True):
   
3.         self.val = val
   
4.         self.left = left
   
5.         self.right = right
   
6.         self.is_asterisk = isAsterisk
   
7.         
   
8. class Solution(object):
   
9.    
   
10.     def _maxPathSum(self, root):
    
11.         # this function only returns path sum using the root, and not using both childs at the same time
    
12.         if not root:
    
13.             return -sys.maxint
    
14.         l = max(0, self._maxPathSum(root.left))
    
15.         r = max(0, self._maxPathSum(root.right))
    
16.         
    
17.         current = root.val
    
18.         if root.left is None and root.right is None and not root.is_asterisk:
    
19.             # convert current node value from int to float, which will be used as an indicator of non-asterisk leaves in path
    
20.             current += 0.0
    
21.         if isinstance(l, int) and isinstance(r, int):
    
22.             self.ans = max(self.ans, l + r + current)
    
23.         return current + max(l, r)
    
24.    
    
25.     def maxPathSum(self, root):
    
26.         import sys
    
27.         self.ans = -sys.maxint
    
28.         self._maxPathSum(root)
    
29.         return self.ans

复制代码

Tree DFS 可以做这个

感谢楼主分享，可以refer这套题。 https://leetcode.com/problems/binary-tree-maximum-path-sum/

力扣八路无应该能做

Yarakk 发表于 2021-9-27 16:45
力扣八路无应该能做

请问是865吗？

先遍历树找到带星号的结点，再找出两两的LCA，然后再算LCA到这两个点的sum，取所有可能的最大值？

这个是不是比124要简单些？只求叶子结点有星号的LCA最大就好了，不需要考虑树中间的结点

Java

1.    class Solution {
   
2.         int max;
   
3. 
   
4.         public int maxPathSum(TreeNode root) {
   
5.             max = Integer.MIN_VALUE;
   
6.             dfs(root);
   
7.             return max;
   
8.         }
   
9. 
   
10.         Integer dfs(TreeNode node) {
    
11.             if (node == null) {
    
12.                 return null;
    
13.             }
    
14. 
    
15.             Integer left = dfs(node.left);
    
16.             Integer right = dfs(node.right);
    
17. 
    
18.             if (left == null && right == null) {
    
19.                 if (node.asterisk) {
    
20.                     max = Math.max(max, node.val);
    
21.                     return node.val;
    
22.                 } else {
    
23.                     return null;
    
24.                 }
    
25.             } else if (left == null) {
    
26. 
    
27.                 int tmp = Math.max(node.val, node.val + right.intValue());
    
28.                 max = Math.max(max, tmp);
    
29.                 return tmp;
    
30.             } else if (right == null) {
    
31.                 int tmp = Math.max(node.val, node.val + left.intValue());
    
32.                 max = Math.max(max, tmp);
    
33.                 return tmp;
    
34.             }
    
35.             int leftValue = left.intValue();
    
36.             int rightValue = right.intValue();
    
37.             if (leftValue > 0 && right > 0) {
    
38.                 max = Math.max(max, node.val + leftValue + rightValue);
    
39.             }
    
40. 
    
41.             if (leftValue > 0 || rightValue > 0) {
    
42.                 int tmp = Math.max(node.val + leftValue, node.val + rightValue);
    
43.                 max = Math.max(max, tmp);
    
44.                 return tmp;
    
45.             } else {
    
46.                 max = Math.max(max, node.val);
    
47.                 return node.val;
    
48.             }
    
49.         }
    
50.     }

复制代码