Skip to content

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

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool isValidSequence(TreeNode* root, vector<int>& arr) {
    return isValidSequence(root, arr, 0);
  }

 private:
  bool isValidSequence(TreeNode* root, const vector<int>& arr, int i) {
    if (root == nullptr)
      return false;
    if (i == arr.size() - 1)
      return root->val == arr[i] && root->left == nullptr &&
             root->right == nullptr;
    return root->val == arr[i] && (isValidSequence(root->left, arr, i + 1) ||
                                   isValidSequence(root->right, arr, i + 1));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public boolean isValidSequence(TreeNode root, int[] arr) {
    return isValidSequence(root, arr, 0);
  }

  private boolean isValidSequence(TreeNode root, int[] arr, int i) {
    if (root == null)
      return false;
    if (i == arr.length - 1)
      return root.val == arr[i] && root.left == null && root.right == null;
    return root.val == arr[i] &&
        (isValidSequence(root.left, arr, i + 1) || isValidSequence(root.right, arr, i + 1));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:
    def isValidSequence(root: Optional[TreeNode], i: int) -> bool:
      if not root:
        return False
      if i == len(arr) - 1:
        return root.val == arr[i] and not root.left and not root.right
      return root.val == arr[i] and (isValidSequence(root.left, i + 1) or isValidSequence(root.right,  i + 1))

    return isValidSequence(root, 0)