Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/532/week-5/3315/
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 <= 50000 <= arr[i] <= 9- Each node's value is between [0 - 9].
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode() {} | |
| * TreeNode(int val) { this.val = val; } | |
| * TreeNode(int val, TreeNode left, TreeNode right) { | |
| * this.val = val; | |
| * this.left = left; | |
| * this.right = right; | |
| * } | |
| * } | |
| */ | |
| class Solution { | |
| public boolean isValidSequence(TreeNode root, int[] arr) { | |
| return dfs(root, 0, arr); | |
| } | |
| private boolean dfs(TreeNode node, int i, int[] arr) { | |
| // We will terminate ie., not recurse after leaf node | |
| if (node == null) { | |
| return false; | |
| } | |
| // Array index out of bounds or mismatch is not allowed | |
| if (i == arr.length || node.val != arr[i]) { | |
| return false; | |
| } | |
| // Leaf node, and last index of array | |
| if (node.left == null && node.right == null) { | |
| return i == arr.length - 1 && arr[i] == node.val; | |
| } | |
| return dfs(node.left, i + 1, arr) || dfs(node.right, i + 1, arr); | |
| } | |
| } |
