[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

문제

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

Return the following binary tree:

3 / \ 9 20 / \ 15 7

 

Approach

Preorder는 부모 -> 왼쪽 -> 오른쪽 순으로 탐색을 하기 때문에

맨 처음에 나오는 원소가 트리의 루트 노드이다

그리고 Inorder는 왼쪽 -> 부모 -> 오른쪽 순으로 탐색하기 때문에

Preorder의 root를 inorder에서 찾으면 그 인덱스를 기준으로 왼쪽트리, 오른쪽 트리로 나눠진다는 것을 알 수 있다.

이를 재귀함수를 통해 트리를 계속 왼쪽 오른쪽으로 나누며 그리면 된다.

또한 inorder를 통해 왼쪽 트리의 노드 개수, 오른쪽 트리의 노드 개수도 알 수 있으므로

Preorder에서 왼쪽 트리와 오른쪽 트리에 들어갈 원소를 적절히 나눠주면 된다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_ConstructBinaryTreeFromPreorderAndInorderTraversal.cpp

chi3236/algorithm