LeetCode 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].

---

给定一棵二叉树，和一个数组，问树中从根节点到叶子节点能否组成给定数组。

简单题，本质就是Trie树，直接DFS查找即可，代码如下：

class Solution {
public:
	bool dfs(TreeNode* root, vector<int>& arr, int idx) {
		int n = arr.size();
		if (idx >= n)return false;
		if (root->val == arr[idx] && root->left == NULL && root->right == NULL && idx == n - 1)return true;
		if (root->val != arr[idx])return false;
		bool left = false, right = false;
		if (root->left != NULL)left = dfs(root->left, arr, idx + 1);
		if (root->right != NULL)right = dfs(root->right, arr, idx + 1);
		return left || right;
	}
	bool isValidSequence(TreeNode* root, vector<int>& arr) {
		if (root == NULL)return false;
		return dfs(root, arr, 0);
	}
};

本代码提交AC，用时104MS。