Algorithm

[leecode] Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

nockdoo 2020. 5. 1. 14:41

- Tree 의 root 노드부터 leaf 노드까지의 노드의 값들이(순서대로) arr의 값이 동일한지 체크하는 문제. 만약 arr[0,1,0,1] 이면 root 노드의 값 0 으로 시작하여 중가 노드는 1 과 0 순서대로 나와야 하고 마지막 노드의 값이 1이여아 함.

- 바이너리 트리(root)를 깊이 우선 탐색(DFS) 하면서 depth level 이 깊어질수록 arr[index++] 의 값이 동일한지 계속 체크.

- arr[arr.length-1] 와 leaf 노드와 같이 일치하면 true 를 반환.

 

let ret
var isValidSequence = function(root, arr) {
    
    ret  = false
    traverse(root, arr, 0)
    return ret
};

var traverse = function(node, arr, index) {
    
    if(node.val !== arr[index]) return
    
    if(!node.left && !node.right && index === arr.length-1) ret = true
    
    if(node.left) traverse(node.left, arr, index+1)
    if(node.right) traverse(node.right, arr, index+1)
    
}