# Binary Tree Maximum Path Sum

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 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

## Solution

• 左子樹或右子樹若小於 0，會造成總和變小，因此當子樹小於 0 時，則設為 0。
• 遞迴時的回傳值只能是左子樹或右子樹的較大值 + root。
• 總和為左子樹 + root + 右子樹，在遞迴過程中不斷更新。

# Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree.

We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.

Example 1:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation:
The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure).
Other valid sequences are:
0 -> 1 -> 1 -> 0
0 -> 0 -> 0

Example 2:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
Output: false
Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.

Example 3:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
Output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence.

Constraints:
1 <= arr.length <= 5000
0 <= arr[i] <= 9
Each node’s value is between [0 - 9].

Hint #1
Depth-first search (DFS) with the parameters: current node in the binary tree and current position in the array of integers.

Hint #2
When reaching at final position check if it is a leaf node.

## Solution

• 多傳入一個變數 i 做為 sequence 的 index。回傳左子樹或右子樹是否為 Valid Sequence。
• 判斷是否為 Valid Sequence 的條件主要有兩個：
• 能從頭到尾 => `i == arr.size() - 1`
• 確認最後是 leaf，不存在左子樹以及右子樹 => `!root->left && !root->right`
• 在遞迴過程中我們要檢查不會是 Valid Sequence 的情形：
• 節點不存在 => `!root`
• 輸入的 sequence 過長 => `i >= arr.size()`
• 值不符 => `root->val != arr[i])`