LeetCode 30 days Challenge - Day 30

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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:

1
2
3

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:

1
2
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].

Solution

题目要求分析：给定一棵二叉树以及一个整型数组，定义从根出发直到叶子结点结束的路径为一个有效序列，且整型数组按照元素位置连接成一个序列，求是否存在一个有效序列与数组确定的序列相同。

解法：

本题原题比较绕口、难以理解，实际上就是从二叉树根出发，寻找一条直达叶子结点的路径，路径上每个结点值依次与给定的整型数组相等。

理解清楚题意后，本题就变得比较简单，DFS即可解决。

这里梳理一下DFS过程中的退出条件，以下称数组确定的序列为目标序列：

当前位置已经超过数组长度：说明该路径还没到达叶子结点就已经超过目标序列的最大长度了，返回false。
当前位置未超过数组长度，且没有左右孩子，为叶子结点：说明当前路径是一个有效序列，且目标序列和该有效序列除了尾部元素其余值一致。因此只需要判断目标序列是否也到达尾部元素，尾部元素值是否与该叶子节点值相等，满足则该有效序列即为目标序列，返回true，反之返回false。
当前位置未超过数组长度，且不是叶子结点，且该位置元素值不等于目标序列对应位置元素值：说明该路径失效，返回false。
当前位置未超过数组长度、不是叶子结点、该位置元素值等于目标序列对应位置元素值：说明迄今为止的路径都满足目标序列的要求，需要接着往下考虑：对存在的孩子结点进行DFS，且只要有一个孩子满足条件就返回true，都不满足才返回false。

以上解释为追求普适性，比较啰嗦，可以直接参考代码，代码可读性较强。

bool dfs(TreeNode* node, vector<int> &arr, int pos) {
    if (pos > arr.size() - 1) return false;
    // leaf
    if (!node->left && !node->right) {
        return (pos == arr.size() - 1 && node->val == arr[pos]);
    }
    // non-leaf
    if (node->val != arr[pos]) return false;
    bool flag = 0;
    if (node->left) flag = dfs(node->left, arr, pos+1);
    if (node->right) flag = flag || dfs(node->right, arr, pos+1);
    return flag;
}
bool isValidSequence(TreeNode* root, vector<int>& arr) {
    return dfs(root, arr, 0);
}

传送门：Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Karl

Karl's Nest

leetcode-day-30

LeetCode 30 days Challenge - Day 30

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

Solution