[Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal

문제 : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

---

이진 트리의 중위 순회, 후위 순회 결과 배열들이 주어졌을 때 이진 트리를 구하라.

---

루트노드는 후위순회의 가장 뒤에 있는 노드이다.

후위순회 배열에서 루트 노드를 구한 뒤 중위 순회에서 루트노드의 왼쪽에 있는 값들이 왼쪽 자식 노드들, 오른쪽에 있는 값들이 오른쪽 자식 노드들이 된다.

중위 순회, 후위 순회 배열들의 범위를 위와 같은 방법으로 줄여나가며 재귀함수로 서브트리들의 루트노드, 왼쪽 오른쪽 자식 노드들을 구하며 트리를 만들어나간다.

 

시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/106.%20Construct%20Binary%20Tree%20from%20Inorder%20and%20Postorder%20Traversal.cpp