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)
}