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

Solution：

```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidSequence(root *TreeNode, arr []int) bool {
return dfs(root, &arr, 0, nil)
}
func dfs( root *TreeNode, arr *[]int, cur int, sib *TreeNode) bool {
switch {
case (cur == len(*arr) && root != nil):
return false
case (cur == len(*arr) && root == nil):
if( sib != nil){ // no leaf
return false
}
return true
case root == nil:
return false
case (*root).Val != (*arr)[cur]:
return false
}
left := dfs(root.Left, arr, cur+1, root.Right)
right := dfs(root.Right, arr, cur+1, root.Left)
return left||right
}
```