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

Explanation

To solve this problem, we can perform a depth-first traversal of the binary tree while keeping track of the current index of the string we are checking. At each node, we check if the current index matches the value at the node. If it does, we recursively check the left and right subtrees with the next index. If we reach a leaf node and the index matches the length of the string, we return true, indicating that the string is a valid sequence from the root to that leaf.

Algorithm:

1. Perform a depth-first traversal of the binary tree.
2. At each node, check if the current index matches the value at the node.
3. If it does, recursively check the left and right subtrees with the next index.
4. If we reach a leaf node and the index matches the length of the string, return true.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the binary tree.

class Solution {
    public boolean isValidSequence(TreeNode root, int[] arr) {
        return isValid(root, arr, 0);
    }
    
    private boolean isValid(TreeNode node, int[] arr, int index) {
        if (node == null || index >= arr.length || node.val != arr[index]) {
            return false;
        }
        
        if (node.left == null && node.right == null && index == arr.length - 1) {
            return true;
        }
        
        return isValid(node.left, arr, index + 1) || isValid(node.right, arr, index + 1);
    }
}