 # 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

{% note success %}

{% endnote %}

• 左子樹或右子樹若小於 0，會造成總和變小，因此當子樹小於 0 時，則設為 0。
• 遞迴時的回傳值只能是左子樹或右子樹的較大值 + root。
• 總和為左子樹 + root + 右子樹，在遞迴過程中不斷更新。
class Solution {
public:
int maxPathSum(TreeNode *root) {
int sum = root->val;
PathSum(root, sum);
return sum;
}

int PathSum(TreeNode *node, int &sum) {
if (!node) return 0;

int left = max(PathSum(node->left, sum), 0);
int right = max(PathSum(node->right, sum), 0);
sum = max(sum, left + node->val + right);

return max(left, right) + node->val;
}
};


</br>

# 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

{% note success %}

{% endnote %}

• 多傳入一個變數 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])
class Solution {
public:
bool isValidSequence(TreeNode *root, vector<int> &arr) {
return isValidSequence(root, arr, 0);
}

bool isValidSequence(TreeNode *root, vector<int> &arr, int i) {
if (!root || (i >= arr.size()) || (root->val != arr[i]))
return false;

if ((i == arr.size() - 1) && !root->left && !root->right)
return true;

return isValidSequence(root->left, arr, i + 1) || isValidSequence(root->right, arr, i + 1);
}
};


</br>

document.write( "");