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

문제

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

알아야 할 개념

• inorder
• postorder

풀이

탐색 순서는 다음과 같다.

preorder : root -> left -> right

inorder : left -> root -> right

postorder : left -> right -> root 

 

주어진 예제 1번을 보면

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

처음에 탐색을 시작할때, 알 수 있는 특징은, postorder의 맨 마지막 원소가 루트 라는 사실이다.(모든 캐이스에서 성립)

postorder : left -> right -> root  순으로 탐색하기 때문에, [start .. end] 구간을 탐색할 때 루트를 먼저 찾는다. 

 

풀이 알고리즘은 다음과 같다. 

1. 루트 인덱스 탐색
2. 재귀로 루트 right 노드 탐색해서 연결
3. 재귀로 루트 left 노드 탐색해서 연결
4. 현재 레벨에서 루트 return

left , right 순이 아닌 right left 순으로 연결하는 이유는 postorderIndex 를 만들어 postorder 뒤에서부터 앞으로 탐색한다.

postorder는 left , right, root 순서니깐 거꾸로 탐색하면 root right left 순이다. 따라서 right를 먼저 탐색해서 연결해준다.

 

코드

class Solution {

    int postIndex ;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length ;
        if(n == 0)return null;
        if(n == 1 )return new TreeNode(inorder[0]);
        postIndex = n-1;
        return helper(inorder, postorder, 0, n-1);
    }
    public TreeNode helper(int[] inorder, int[] postorder, int start, int end){
        if(start  > end  || postIndex<0) return null;
        TreeNode root = new TreeNode(postorder[postIndex--]);
        int rootIndex = findN(inorder, root.val);
        
        root.right = helper(inorder, postorder, rootIndex+1, end);
        root.left = helper(inorder, postorder, start, rootIndex-1);
        
        return root;
    }
    public int findN(int[] arr, int key){
        for(int i = 0 ;i < arr.length ;i++){
            if(arr[i] == key)return i;
        }
        return -1;
    }
}