Leetcode題解 Python & C#：四月挑戰DAY30 Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

給一串二進位二元樹跟一串二進位數列，是否能依數列的值到達葉(leaf)，也就是底層。

這算是「搜尋法」，只要有基本的暴力破解法觀念也可以順利解出。

如果要優化時空，使用遞迴函數就可以快速解出。

Python

class Solution:
    def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
        if root and arr and root.val == arr[0]:
            if len(arr) == 1 and root.right is None and root.left is None: return True
            return self.isValidSequence(root.left, arr[1:]) or self.isValidSequence(root.right, arr[1:]) 
        else:
            return False

C#

public class Solution {        
    public bool IsValidSequence(TreeNode root, int[] arr) {
        int l = 0; 
        int r = arr.Length;
        var stack = new List(){root};
        while(l < r && stack.Count>0)
        {
            int n = stack.Count;
            for(int i = 0; i < n; i++)
            {
                var node = stack[0];
                if(node.val==arr[l])
                {
                    if(l == r-1 && node.left is null && node.right is null)
                        return true;
                    if(!(node.left is null)){stack.Add(node.left);}
                    if(!(node.right is null)){stack.Add(node.right);}                        
                }                
                stack.RemoveAt(0);
            }
            l++;
        }
        return false;
    }
}