DAY 19
1
Software Development

## [Day 19] 從LeetCode學演算法 - 0124. Binary Tree Maximum Path Sum (Hard)

``````Question:
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along with the parent-child connections. The path must contain at least one node and does not need to go through the root.
``````
``````Example 1:
Input: [1,2,3]
1
/ \
2   3
Output: 6
``````
``````Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9  20
/  \
15   7
Output: 42
``````

3~

2~

1~

(這邊指從雙方往上走第一個碰頭的位置)，再走下來才行。

(如前面的範例就都是其他節點，

(因為l或r都有可能是負的，所以要把這四種都考慮在內)

(因為n.val+l+r代表這個點是做為中繼點才會有分支)

(一直到最底下才能回頭依序得到各自的l跟r)，

``````define res
maxPathSum(root){
res = root.val
dfs(root)
return res
}
dfs(n){
l = (n.left != NIL) ? dfs(n.left) : 0
r = (n.right != NIL) ? dfs(n.right) : 0
m = n.val
m = max(m, l + m, r + m) // 單做為經過點的最大路徑和
res = max(res, m, l + r + n.val) // m已比過3種可能，故只需再考慮中繼點
return m
}
``````

Java的部分，這邊使用了if來作比較，

Java:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res;
public int maxPathSum(TreeNode root) {
res = root.val;
dfs(root);
return res;
}
public int dfs(TreeNode n) {
int l = (n.left != null) ? dfs(n.left) : 0;
int r = (n.right != null) ? dfs(n.right) : 0;
int m = n.val;
if (l > r)
m = Math.max(m, l + m);
else
m = Math.max(m, r + m);

if (m > l + r + n.val)
res = Math.max(res, m);
else
res = Math.max(res, l + r + n.val);
return m;
}
}
``````

Python的部分，留意呼叫時加上的self.即可，

Python:

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def __init__(self):
self.res = 0

def maxPathSum(self, root: TreeNode) -> int:
self.res = root.val
self.dfs(root)
return self.res

def dfs(self, n: TreeNode) -> int:
l = self.dfs(n.left) if n.left else 0
r = self.dfs(n.right) if n.right else 0
m = max(n.val, l + n.val, r + n.val)
self.res = max(self.res, m, l + r + n.val)
return m
``````

「時間/空間複雜度？」
(每個節點均會走過一遍，故時間複雜度為O(N)

0111. Minimum Depth of Binary Tree (Easy)