[LeetCode] 105번 - Construct Binary Tree from Preorder and Inorder Traversal [Swift]

문제 링크

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.

문제 풀이

이 문제는 주어진 전위 순회와 중위 순회로 완전 이진트리 형태로 나타내는 문제입니다.

전위 순회와 중위 순회의 특징을 활용하여 문제를 풀면 됩니다.

 

그럼 간단하게 각 순회의 특징을 짚고 넘어가 보겠습니다.

위와 같이 중위 순회는 어떤 값이 루트 노드의 값일 때 해당 값의 왼쪽, 오른쪽의 값들이 왼쪽에 위치한 노드, 오른쪽에 위치한 노드입니다.

예를 들어 위의 예에서는 3번 노드가 루트 노드인데 중위 순회에서 3의 왼쪽에 해당하는 9는 3번 노드의 왼쪽에 위치하고 3의 오른쪽에 위치하는 15, 20, 7의 경우에는 3번 노드의 오른쪽에 위치하는 것을 볼 수 있습니다.

그리고 전위 순회의 경우 루트 노드 순서대로 정렬된 것을 볼 수 있어요

 

즉 위와 같은 특징을 사용하여 아래와 같은 단계를 수행하면 됩니다.

1. 전위 순회에서 루트 노드를 가지고 옵니다.
2. 가지고 온 루트 노드를 중위 순회에서 찾고 왼쪽, 오른쪽을 나눕니다.
3. 2번에서 나눈 왼쪽 부분을 가지고 1번부터 다시 수행합니다.
4. 2번에서 나눈 오른쪽 부분을 가지고 1번 부터 다시 수행합니다.

이렇게 분할 정복으로 답을 구할 수 있습니다!

소스 코드

class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.count < 2 {
            return TreeNode(preorder[0])
        }
        
        var preIndex: Int = 0
        
        func makeTreeNodes(nowRoot: TreeNode?, inorder: [Int]) -> TreeNode? {
            if preIndex >= preorder.count {
                return nil
            }
            if inorder.count == 0 {
                return nil
            }
            // 현재 루트의 값을 전위 순회에서 가져옵니다.
            nowRoot?.val = preorder[preIndex]
            var left: [Int] = []
            var right: [Int] = []
            
            // 현재 루트의 값을 중위 순회에서 찾습니다.
            for i in 0..<inorder.count {
                if preorder[preIndex] == inorder[i] {
                    left = Array(inorder[0..<i])
                    right = Array(inorder[i+1..<inorder.count])
                    break
                }
            }
            preIndex += 1
            
            // 현재 루트 노드의 왼쪽 부분에 대하여 다시 반복합니다.
            nowRoot?.left = makeTreeNodes(nowRoot: TreeNode(), inorder: left)
            // 현재 루트 노드의 오른쪽 부분에 대하여 다시 반복합니다.
            nowRoot?.right = makeTreeNodes(nowRoot: TreeNode(), inorder: right)
            
            return nowRoot
        }
        
        
        return makeTreeNodes(nowRoot: TreeNode(), inorder: inorder)
    }
}