Leetcode - 105. Construct Tree from Preorder and Inorder Traversal

---

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

 

 

Answer

 

Preorder는 Root가 우선해서 순회하는 방식이다 즉 ( Root, Left, Right ) 순으로 순회하고

Inorder는 Root를 중간에 순회하는 방식으로 ( Left, Root, Right ) 순으로 순회한다

 

 

Inorder 방식의 순회한 결과를 본다면 현재 Root를 기준으로 어떤게 Left 서브트리 안에 들어가고 

어떤게 Right 서브트리 안에 들어가는지 알 수 있다.

 

 

예를 들면

Inorder 순회 결과가 [1, 9, 3, 15, 20, 7]인 트리가 있고 이 트리의 Root가 3이라고 할때

위와같이 루트 값 '3'을 기준으로 좌측 트리와 우측 트리를 나눌 수 있게 된다.

 

 

따라서 트리를 구축할때 Inorder의 이런 성질과

Preorder는 루트부터 확인한다는 성질을 이용해서 코드를 구축해내면 된다.

 

 

Preorder array를 순차적으로 조회하여 트리를 구축하고 현재 구축하고 있는 트리가 좌측 트리인지 우측 트리인지는 Inorder 순회결과를 이용하여 문제를 풀면 된다.

 

 

 

---

Reference

 

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode