[Java] Daily LeetCode Challenge 106. Construct Binary Tree from Inorder and Postorder Traversal

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

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

 

postorder은 root가 마지막에 나오고, inorder은 root가 가운데 나온다.

 

방법

1. inorder 배열에서 root 중심으로 앞 뒤 나눠서 HashSet에 저장

2. postorder에서 각 HashSet에 들어있는 숫자중에 idx가 가장 높은 점을 찾아냄 (해당 branch의 root임)

3. root 중심으로 다시 1번부터 dfs 진행

 

 

[코드]

/**
 * 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 {
    public int[] inorder, postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;

        TreeNode root = setChild(postorder.length-1, 0, postorder.length-1);
        return root;
    }

    public TreeNode setChild(int rootIdx, int start, int end){
        TreeNode root = new TreeNode(postorder[rootIdx]);

        HashSet<Integer> pre = new HashSet<Integer>();
        HashSet<Integer> aft = new HashSet<Integer>();
        
        int mid = -1;
        for(int i=start; i<=end; i++){
            if(inorder[i]==root.val){
                mid = i;
                continue;
            }

            if(mid==-1)
                pre.add(inorder[i]);
            else
                aft.add(inorder[i]);
        }

        if(pre.size()>0)
            root.left = setChild(getRootIdx(pre), start, mid-1);
        if(aft.size()>0)
            root.right = setChild(getRootIdx(aft), mid+1, end);
        
        return root;
    }

    public int getRootIdx(HashSet<Integer> hs){
        boolean findRange = false;

        int end=-1;
        for(int i=0; i<postorder.length; i++){
            if(hs.contains(postorder[i])){
                if(!findRange)
                    findRange = true;
                end = i;
            }else if(findRange){
                break;
            }
        }

        return end;
    }
}