本週題目
- Binary Tree Maximum Path Sum
- Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
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 %}
通常 binary tree 的題型都適用遞迴法:
{% 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 -> 0Example 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 %}
通常 binary tree 的題型都適用遞迴法:
{% 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>
- Source code: george16886@GitHub
- [x] Programming language: C++
- [x] Environment: ubuntu 16.04
- [x] Tool: Visual Studio Code
- Category: 30-Day LeetCoding Challenge
- Original post @george16886's blog