[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal - Java

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

---

문제

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

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

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

 

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

---

풀이

풀이 과정

이진 트리의 전위 순회 배열 preorder와 같은 트리의 중위 순회 배열 inorder배열이 주어졌을 때, 원래의 이진 트리를 구하는 문제이다.

우선 이진트리의 전위 순회와 중위 순회의 특징에 대해서 살펴보면
전위 순회의 경우 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 탐색을 하게 되고
중위 순회의 경위 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순으로 탐색을 하게 된다.

따라서 전위 순회의 첫 노드는 이진트리의 root 노드가 되고 중위 순회 배열에서 이 root 노드를 기준으로 왼쪽에 있는 값들은 root 노드의 왼쪽 노드 값, 오른쪽에 있는 값들은 root 노드의 오른쪽 노드 값이 된다.
그림으로 살펴보면 아래와 같다.

이후에 왼쪽 노드와 오른쪽 노드에 대해서 같은 과정을 재귀 탐색하면 최종적으로 원래의 이진트리의 모습을 구할 수 있다.
해당 과정을 구현하는 과정과 코드는 다음과 같다.

재귀 탐색을 위한 함수를 생성한다. 

/**
    * @param preorder      전위 순회 배열
    * @param inorder       중위 순회 배열
    * @param preIndex      preorder 배열에서 현재 노드의 인덱스
    * @param inStart       현재 탐색중인 inorder 배열의 시작 인덱스
    * @param inEnd         현재 탐색중인 inorder 배열의 종료 인덱스
    * @return              TreeNode
    */
    public TreeNode makeTree(int[] preorder, int[] inorder, int preIndex, int inStart, int inEnd) {
    
    }

 

우선 preorder 배열에서 현재 노드의 인덱스가 배열의 크기를 벗어나거나 inorder 배열의 시작 인덱스가 종료 인덱스보다 큰 경우 더 이상 하위 노드가 존재하지 않으므로 null을 return하여 탐색을 종료한다.

// preorder 배열에서 현재 노드의 인덱스가 배열의 크기를 벗어나거나
// inorder 배열의 시작 인덱스가 종료 인덱스보다 큰 경우 더 이상 노드가 존재하지 않으므로 null을 return
if(preIndex > preorder.length || inStart > inEnd) return null;

 

 

그렇지 않은 경우 preorder 배열에서 현재 노드의 인덱스 값에 해당하는 값으로 새 노드를 생성한다.

// 새로운 트리노드 생성
TreeNode node = new TreeNode(preorder[preIndex]);

 

현재 노드의 값을 기준으로 inorder 배열에서 현재 노드값에 해당하는 인덱스를 탐색한다. 이 인덱스를 기준으로 왼쪽과 오른쪽에 들어갈 노드를 나누게 된다.

// inorder 배열에서 현재 노드의 인덱스 탐색
// 해당 인덱스를 기준으로 노드를 좌우로 나눔
int inIndex = 0;

for(int i = inStart; i <= inEnd; i++) {
    if(node.val == inorder[i]) {
        inIndex = i;
        break;
    }
}

 

현재 노드의 왼쪽 오른쪽 노드에 해당하는 노드를 만들기 위해 함수를 재귀 호출하고 현재 노드를 return 한다.

// 현재 노드의 좌우 노드 추가
// 왼쪽 노드의 인덱스 = preorder 배열에서 현재 노드의 다음 인덱스
// 왼쪽 노드의 시작 인덱스 = inorder 배열의 시작 인덱스
// 왼쪽 노드의 종료 인덱스 = inorder 배열에서 현재 노드의 인덱스 - 1
node.left = makeTree(preorder, inorder, preIndex + 1, inStart, inIndex - 1);
// 오른쪽 노드의 시작 인덱스 = preorder 배열에서 현재 노드의 인덱스(preIndex) + inorder 배열에서 왼쪽 노드의 수(inIndex - inStart + 1)
// 오른쪽 노드의 시작 인덱스 = inorder 배열에서 현재 노드의 인덱스 + 1
// 오른쪽 노드의 종료 인덱스 = inorder 배열의 종료 인덱스
node.right = makeTree(preorder, inorder, preIndex + inIndex - inStart + 1, inIndex + 1, inEnd);

return node;

---

최종 코드

/**
 * 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) {
        return makeTree(preorder, inorder, 0, 0, inorder.length - 1);
    }

    /**
    * @param preorder      전위 순회 배열
    * @param inorder       중위 순회 배열
    * @param preIndex      preorder 배열에서 현재 노드의 인덱스
    * @param inStart       현재 탐색중인 inorder 배열의 시작 인덱스
    * @param inEnd         현재 탐색중인 inorder 배열의 종료 인덱스
    * @return              TreeNode
    */
    public TreeNode makeTree(int[] preorder, int[] inorder, int preIndex, int inStart, int inEnd) {
        
        // preorder 배열에서 현재 노드의 인덱스가 배열의 크기를 벗어나거나
        // inorder 배열의 시작 인덱스가 종료 인덱스보다 큰 경우 더 이상 하위 노드가 존재하지 않으므로 null을 return
        if(preIndex > preorder.length || inStart > inEnd) return null;
        
        // 새로운 트리노드 생성
        TreeNode node = new TreeNode(preorder[preIndex]);
        
        // inorder 배열에서 현재 노드의 인덱스 탐색
        // 해당 인덱스를 기준으로 노드를 좌우로 나눔
        int inIndex = 0;
        
        for(int i = inStart; i <= inEnd; i++) {
            if(node.val == inorder[i]) {
                inIndex = i;
                break;
            }
        }
        
        // 현재 노드의 좌우 노드 추가
        // 왼쪽 노드의 인덱스 = preorder 배열에서 현재 노드의 다음 인덱스
        // 왼쪽 노드의 시작 인덱스 = inorder 배열의 시작 인덱스
        // 왼쪽 노드의 종료 인덱스 = inorder 배열에서 현재 노드의 인덱스 - 1
        node.left = makeTree(preorder, inorder, preIndex + 1, inStart, inIndex - 1);
        // 오른쪽 노드의 시작 인덱스 = preorder 배열에서 현재 노드의 인덱스(preIndex) + inorder 배열에서 왼쪽 노드의 수(inIndex - inStart + 1)
        // 오른쪽 노드의 시작 인덱스 = inorder 배열에서 현재 노드의 인덱스 + 1
        // 오른쪽 노드의 종료 인덱스 = inorder 배열의 종료 인덱스
        node.right = makeTree(preorder, inorder, preIndex + inIndex - inStart + 1, inIndex + 1, inEnd);
        
        return node;
    }
}

---