105. Construct Binary Tree from Preorder and Inorder Traversal

문제

int[] 형 배열로 전위순회(preorder), 중위순회(inorder) 값이 주어졌을때 Binary Tree 를 만드는 문제이다.

 

int[] preorder = {3, 9, 20, 15, 7};

int[] inorder = {9, 3, 15, 20, 7};

 

TreeNode node = [3, 9, 20, null, null, 15, 7];

 

문제 풀이

전위순회, 중위순회, 후위순회 중 2가지 이상이 있다면 트리를 생성할 수 있다.

 

먼저 전위순회가 기준이 된다.

전위순회의 원소를 하나씩 가지고 와서 중위순회에 몇번째에 위치한지 인덱스를 찾는다.

 

이 인덱스가 루트노드가 되고,

해당 인덱스 기준으로 왼쪽이 왼쪽 자식노드들이 되고,

해당 인덱스 기준으로 오른쪽이 오른쪽 자식노드들이 된다.

 

예를 들어, 아래와 같이 0부터 4개의 원소가 각각 있을때

preorder : 3, 9, 20, 15, 7 

inorder : 9, 3, 15, 20, 7

 

첫번째 preoder 의 0번째 원소인 3 값은 inorder 의 1번째에 위치해있다.

inoder 의 1번째 위치의 왼쪽 자식은 9 하나밖에 없고,

inorder 의 1번째 위치의 오른쪽 자식은 15, 20, 7이 된다.

 

왼쪽 자식은 9 하나 밖에 없기 때문에 9 값을 왼쪽 노드에 추가하고,

오른쪽 자식에 노드를 추가하는 로직을 수행한다.

오른쪽 자식 노드 추가하는 방식은 기존과 동일하다.

코드

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTree(preorder, inorder, 0, inorder.length-1);        
}

int preIndex = 0;

public TreeNode buildTree(int[] pre, int[] in, int start, int end) {
    if(start > end) return null;

    TreeNode node = new TreeNode(pre[preIndex++]);

    if(start == end) return node;

    int idx = 0;
    for(int i=start; i<=end; i++) {
        if(in[i] == node.val) {
            idx = i;
            break;
        }
    }

    node.left = buildTree(pre, in, start, idx-1);
    node.right = buildTree(pre, in, idx+1, end);
    return node;
}

 

1. if(start > end) return null;

 

노드의 개수가 부족하여 npe 에러를 발생시킬 수 있기 때문에 start 값이 end 값 보다 큰지 체크하는 로직을 추가한다. 

예를들어, preorder = [1, 2], inorder = [2, 1] 값을 주고 로직을 실행시켰을 경우 노드의 개수는 2개 밖에 없지만,

루트 노드의 오른쪽 자식 노드까지 추가하는 로직을 실행시키기 때문에 npe 에러가 발생할 수 있다. (node.right = buildTree... 로직)

 

2. preoder 배열의 값을 하나씩 꺼내어 루트노드로 만든다.

 

3. start == end 값이 동일하면 자식 노드가 없는것으로 보고 리턴

 

4. preoder 배열의 값(루트) 이 inorder 배열의 몇번째에 위치한지 찾는다.

해당 위치를 기준으로 node.left, node.right 노드 값을 추가한다.