30daychallenge (30!) | Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

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

Đề bài dài mà ví dụ cũng dài nhỉ. Bài cuối rồi, nhưng không có nhiều bất ngờ, ở bài này, mình duyệt DFS từ root đến leaf hoặc khi arr.length < = i. Ở đây mình dùng i để so sánh với mỗi path từ nốt mình duyệt xem có giống với thứ tự mảng hay không.

	// duynotes.blogspot.com
	/**
	* 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 root, int i, int[] arr){
	if (root == null || i>arr.length-1){
	return false;
	}
	if (root.val != arr[i]){
	return false;
	}
	if (root.left == null && root.right == null && i == arr.length-1 && root.val == arr[i]){
	return true;
	}
	return DFS(root.left,i+1,arr) || DFS(root.right,i+1,arr);
	}
	}

view raw BinaryTreeValidSequencePath.java delivered with ❤ by emgithub

Hết rồi. Đây là bài cuối rồi, nay mình sẽ nghĩ xem challenge tiếp theo sẽ là gì. Cảm ơn bạn đã đồng hành. Cảm ơn. Cảm ơn. Cảm ơn !