30-Day LeetCoding Challenge 2020 April Week 5 || Leetcode 解題


Posted by george16886 on 2020-05-03

本週題目

  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

{% 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 -> 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 %}
通常 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>


document.write( "");

#Leetcode #Visual Studio Code #30-Day LeetCoding Challenge #C++ #cpp #cplusplus #Leetcode-practice #Leetcode-solution









Related Posts

[MSSQL] 啟動失敗 10013

[MSSQL] 啟動失敗 10013

W13_作業四簡答題

W13_作業四簡答題

Day02 典型統計應用在社群媒體分析(Classical statistics applied to social data) part 2

Day02 典型統計應用在社群媒體分析(Classical statistics applied to social data) part 2


Comments