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
}