题目大意：
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 <= 50000 <= arr[i] <= 9- Each node’s value is between [0 – 9].
本题是Leetcode 2020年4月份每天挑战中的一道题目。我们之前无数次强调过，对于二叉树题目，应该下意识想到使用dfs或者bfs来解题。本题也不例外，使用dfs解题会非常简单。我们只需要从根节点dfs向每个叶子节点，找到一条路径与给定数组完全一致即可。
对于任意非叶子节点，如果当前节点的值与当前index（与根节点的距离）对应数组的值不同的话，直接返回false。如果相同的话，我们可以继续向下dfs，即递归至左子节点以及右子节点，两者只要有一方返回true，本层递归即可返回true。
dfs的终止条件是当遇到叶子节点时（左右子节点都是空），看当前叶子节点所在的index（与根节点的距离），如果该index正好是数组中的最后一位，并且该节点值等于数组中最后一位的话，返回true。否则返回false。另外，如果到达叶子节点时index不是数组最后一位，或者到达数组最后一位时，当前节点不是叶子节点，这都属于不合理的路径，返回false。
实现代码：
public boolean isValidSequence(TreeNode root, int[] arr) {
return help(root, arr, 0); // 递归dfs求解
}
public boolean help(TreeNode root, int[] arr, int index) {
// 当前是叶子节点，并且index是数组最后一位
if(root.left==null&&root.right==null&&index==arr.length-1){
// 返回当前节点值是否等于数组最后一位
return root.val==arr[index];
}
// 如果当前是叶子节点，但index不是最后一位
// 或者当前不是叶子，但是index却是最后一位，返回false
if(root.left==null&&root.right==null||index==arr.length-1){
return false;
}
// 如果当前节点不等于数组当前index的值，返回false
if(root.val != arr[index]) return false;
// dfs至左子节点
if(root.left!=null && help(root.left,arr,index+1)) return true;
// dfs至右子节点
if(root.right!=null && help(root.right,arr,index+1)) return true;
return false;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree.
Memory Usage: 40 MB, less than 100.00% of Java online submissions for Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree.
Runtime: 0 ms
Memory Usage: 40 MB
Accepted Solutions Runtime Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Accepted Solutions Memory Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree-解题思路分析/