Doordash Phone Screen

1. private static int max = Integer.MIN_VALUE;
   
2.     private static int maxPathSum(TreeNode root) {
   
3.         dfs(root);
   
4.         return max;
   
5.     }
   
6.    
   
7.     // Use Integer as return type to distinguish between a true MIN_VALUE or it's null
   
8.     public static Integer dfs(TreeNode node) {
   
9.         if (node == null)
   
10.             return null;
    
11.         // find the alive node, return its value
    
12.         if (node.left == null && node.right == null && node.hasAst) {
    
13.             return node.val;
    
14.         }
    
15.         int val = node.val;
    
16.         Integer left = dfs(node.left);
    
17.         Integer right = dfs(node.right);
    
18.         // if both children are not null, means we find a path that travels from one alive node to another
    
19.         if (left != null && right != null) {
    
20.             max = Math.max(max, left + val + right);
    
21.         }
    
22.         Integer leftMax = left == null ? null : left + val;
    
23.         Integer rightMax = right == null ? null : right + val;
    
24.         // if either leftMax or rightMax is null, it means one of these path is not leading to an alive node, so return the non null path max
    
25.         if (leftMax == null || rightMax == null)
    
26.             return leftMax != null ? leftMax : rightMax;
    
27.         return Math.max(leftMax, rightMax);
    
28.     }

复制代码

xiaozhuxiaozhu 发表于 2021-9-10 19:06
感谢分享， 如果我理解题意了。 这题可能可以直接用recursion做。 第一问。 下面代码是考虑了负数的存在， ...

您好，请问follow up的话在您的思路基础上应该怎么改呢？谢谢。

xiaozhuxiaozhu 发表于 2021-9-10 16:06
感谢分享， 如果我理解题意了。 这题可能可以直接用recursion做。 第一问。 下面代码是考虑了负数的存在， ...

"两个alive nodes路径上不能有其它的alive nodes" => 你的算法不符合这个要求。