💬 문제
어떤 트리의 전위 순회로 읽었을 때의 값 배열 preorder
중위 순회로 읽었을 때의 값 배열 inorder
두 배열을 참고하여 트리를 생성한 후 root 노드 반환
✍️ 나의 풀이
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
if (preorder.length === 0)
return null;
let root = preorder.shift();
let res = new TreeNode(root, null, null);
let idx = inorder.indexOf(root);
res.left = buildTree(preorder.slice(0, idx), inorder.slice(0, idx));
res.right = buildTree(preorder.slice(idx), inorder.slice(idx + 1));
return res;
};재귀함수를 활용하여 root 노드부터 생성, 왼쪽 자식 트리를 완성하여 붙이고
이후에 오른쪽 자식 트리를 완성하여 붙이는 방식
inorder의 root 노드 값 인덱스를 기준으로 왼편은 root의 왼쪽 자식 트리
오른편은 오른쪽 자식 트리의 값들이므로 각 재귀함수에 slice하여 넘겨줌
preorder도 같은 인덱스를 기준으로 나누는데,
이미 노드 한 개가 shift로 빠진 상태이므로 slice 기준 인덱스에 +1하지 않아도 됨
📌 결과
Accepted
Runtime 109ms (Beats 57.50%)
Memory 126.85MB (Beats 23.26%)
📚 러닝 포인트
트리의 전위 순회(Preorder)는 Root-Left-Right 순서이고, 중위 순회(Inorder)는 Left-Root-Right이다. 우리는 Root부터 시작하여 트리를 만들어나가야 하므로 전위 순회의 맨 앞 노드를 시작으로 한다. 그리고 중위 순회 배열 속 해당 노드를 기준으로 왼쪽 자식, 오른쪽 자식을 나눈다. 다시 두 자식이 서브 트리의 Root가 되어 과정을 반복하는 방식으로 트리를 완성할 수 있다. 중위 순회 배열에서는 왼편 오른편을 나눌 수 있는 기준이 있으나, 전위 순회는 어디까지가 한 묶음인지 알 수 없다. 하지만 서브 트리를 이루는 노드의 개수는 같으므로 중위 순회 배열에서 구한 한 묶음의 노드 개수만큼 전위 순회 배열에서 묶으면 된다. Root-Left-Right 순서이므로 앞의 묶음이 왼편, 뒤의 묶음이 오른편이 된다. 이 부분이 문제 해결에 있어 가장 중요한 키포인트였던 것 같다! 재귀 함수를 구현하는 것은 트리 문제를 풀면서 많이 해왔으므로 어렵지 않았다.
