本週題目

  1. Binary Tree Maximum Path Sum
  2. 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

通常 binary tree 的題型都適用遞迴法：

  • 左子樹或右子樹若小於 0，會造成總和變小，因此當子樹小於 0 時，則設為 0。
  • 遞迴時的回傳值只能是左子樹或右子樹的較大值 + root。
  • 總和為左子樹 + root + 右子樹，在遞迴過程中不斷更新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
    }
};

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

通常 binary tree 的題型都適用遞迴法：

  • 多傳入一個變數 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])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
    }
};