Problem
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]Example 2:
Input: inorder = [-1], postorder = [-1] Output: [-1]Constraints:
・ 1 <= inorder.length <= 3000 ・ postorder.length == inorder.length ・ -3000 <= inorder[i], postorder[i] <= 3000 ・ inorder and postorder consist of unique values. ・ Each value of postorder also appears in inorder. ・ inorder is guaranteed to be the inorder traversal of the tree. ・ postorder is guaranteed to be the postorder traversal of the tree.
Idea
Binary Tree 관련된 문제가 연속으로 등장했는데 두 문제 다 못 풀었다. 재귀함수를 다루는데 어느 정도 일가견이 있는 줄 알았으나, 아직까지 갈 길이 멀다. 요새 컨디션이 좋지 않은 것도 한 몫 했겠지만 🥲
inorder와 postorder를 이용해 Binary Tree를 만드는 문제다. postorder를 잘 보면 가장 끝에 있는 값이 root 노드의 값인 것을 알 수 있다. postorder를 역순으로 보면 root 다음 노드가 right subtree의 root 노드다. postorder가 left→right→root 순으로 값을 표시하는 것을 생각하면 역순으로 생각했을 때 역순으로 출력되는 것도 당연한 원리다.
이 원리를 이용해 tree의 root부터 차례대로 만들 수 있다.
우선 inorder의 index를 매번 찾는 것을 방지하기 위해 map에 inorder 값을 key로, index를 value로 넣는다.
재귀함수는 inorder의 startIndex와 endIndex를 인자로 받는다. 그리고 postIndex는 class의 멤버 변수로 설정하는데, 이는 postIndex를 역순으로 탐색하기 위함이다.
재귀함수에서는 postIndex에 해당하는 값으로 노드를 만들어준다. 다음으로 map에서 inorder의 index를 얻은 뒤 curIndex로 저장한다. curIndex를 기준으로 현재 노드의 left subtree와 right subtree를 만들 수 있다.
postorder를 역순으로 탐색하기 때문에 현재 노드의 오른쪽 자식 노드부터 재귀함수를 이용해 설정한다. 재귀함수를 타면서 새로운 노드가 postorder의 역순으로 만들어지며 해당 노드는 부모 노드의 자식노드가 된다. 위 과정을 index 범위가 유효할 때까지 반복하면 binary tree가 완성된다.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int[] inorder;
int[] postorder;
int postIndex;
Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
postIndex = inorder.length - 1;
map = new HashMap<>();
for (int i=0; i <= postIndex; i++) {
map.put(inorder[i], i);
}
return traverseTree(0, postIndex);
}
private TreeNode traverseTree(int startIndex, int endIndex) {
if (startIndex > endIndex || postIndex < 0)
return null;
TreeNode root = new TreeNode(postorder[postIndex--]);
int curIndex = map.get(root.val);
root.right = traverseTree(curIndex+1, endIndex);
root.left = traverseTree(startIndex, curIndex-1);
return root;
}
}Reference
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
