Leet code (Medium): 105. Construct Binary Tree from Preorder and Inorder Traversal - Java

 

배열이 두가지가 주어지고, 두가지 배열이 뭔지 알려준 뒤, 트리를 만들라고 한다.

모든 노드의 value는 유니크 하다고 한다.

 

preorder, inorder 이렇게 두가지가 주어지는데, 분석을 해봤을때, 두 트리의 특성은 다음과 같다.

• preorder: 트리를 위 레벨에서 아래 레벨 순서로 null이 아닌 노드의 value들을 담은 배열
• inorder: 트리를 왼쪽 노드에서 오른쪽 노드로 null이 아닌 노드의 value들을 담은 배열

preorder의 단점은 노드가 어느 노드의 자식으로 붙어야하는지 모른다는 것이고,

inorder의 단점은 특정 요소를 하나 찍었을 때, 그보다 왼쪽에 있는 것들이 트리 상 왼쪽이라는 것만 알지, 부모인지, 자식인지, 같은 레벨의 left인지 등 알수 없다는 것이다.

 

그럼 이 두가지가 서로 상호보완이 가능하다.

preorder는 트리를 순서대로 담고 있으므로, 뭐가 위에 있고 뭐가 아래에 있는것은 알고, inorder는 왼쪽인지 오른쪽인지 알기 때문이다.

 

따라서, preorder를 Queue를 만들어서 담고, inorder에서 queue의 젤 위(앞)에서 부터 index를 찾아가며 트리를 완성한다.

 

 

/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        Queue<Integer> preorderQueue = new LinkedList<>();
        // preorder 하나하나 deque에 넣음 (트리의 위->아래 순서)
        for(int val : preorder){
            preorderQueue.offer(val);
        }

        return build(preorderQueue, inorder);
    }

    // 재귀로 TreeNode를 만들면서 트리형태로 만듦.
    private TreeNode build(Queue<Integer> preorder, int[] inorder){
        // 전달받은 inorder의 길이가 0보다 크면 수행.
        // 가장 왼쪽 노드이거나 가장 오른쪽 노드이면 수행 X.
        if(inorder.length > 0){
            int idx = indexOf(inorder, preorder.poll());    // preorder의 노드의 inorder에서의 index를 찾음.
            TreeNode root = new TreeNode(inorder[idx]);     // 해당 값을 value로 노드 생성함.

            // 노드의 왼쪽은 inorder에서 현재 노드 value의 왼쪽만 새 배열로 만들어서 진행.
            root.left = build(preorder, Arrays.copyOfRange(inorder, 0, idx));   
            // 노드의 오른쪽은 inorder에서 현재 노드 value의 오른쪽만 새 배열로 만들어서 진행.
            root.right = build(preorder, Arrays.copyOfRange(inorder, idx+1, inorder.length));

            return root;
        }

        return null;
    }

    // arr에서 value와 일치하는 요소의 인덱스를 찾음. 없으면 -1리턴.
    private int indexOf(int[] arr, int value){
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == value){
                return i;
            }
        }
        return -1;
    }
}