Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 105. Construct Binary Tree from Preorder and Inorder Traversal

HEESOO on Leetcode

👀 문제

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

👊 도전

1. 설계

  1. inorder에서 preorder[i] 위치를 찾는다. 그 왼쪽은 모두 preorder의 left이고, 오른쪽은 right이다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 *
 * @author HEESOO
 *
 */
/**
 * 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 {
    HashMap<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        
        return solution(0, preorder.length-1, 0, inorder.length-1, preorder, inorder);
    }
    
    public TreeNode solution(int prestart, int preend, int instart, int inend, int[] preorder, int[] inorder){
        if(prestart>preend || instart>inend) return null;
        
        TreeNode node=new TreeNode(preorder[prestart]); // 현재 생성할 노드
        int inroot=map.get(preorder[prestart]); // inorder에서 pre[i]의 위치 찾기
        int left=inroot-instart; // node의 마지막 left 위치 찾기
        
        // left 생성
        node.left=solution(prestart+1, prestart+left, instart, inroot, preorder, inorder);
        // right
        node.right=solution(prestart+left+1, preend, inroot+1, inend, preorder, inorder);
        
        return node;
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. preorder[i]가 inorder에서 몇 번째 인덱스인지 찾는다
    • 반복문으로 인덱스를 찾는 것 보다 해시맵에 넣어서 찾는 것이 더 빠르다.
    • preorder은 VLR, inorder은 LVR으로, preorder 순서대로 트리를 만들되, 어디까지가 left, right인지 확인하기 위해 inorder에서 Visit node의 위치를 찾는다.
    • inorder[preorder[i]]의 왼쪽이 left node이고, 오른쪽이 right 노드이다.
    • left 변수에 node의 마지막 left node 인덱스 번호를 저장한다.
    • preorder 배열에서 prestart+1~prestart+left 인덱스까지가 node의 left node이다.
    • node의 right node들은 prestart+left+1부터 preend까지이다. 이때 node의 left, right를 연결했으므로 다음 node를 찾기 위해 inorder의 범위도 갱신한다.

👏 해결 완료!