LeetCode 알고리즘 Construct Binary Tree from Preorder and Inorder Traversal

안녕하세요 :) 오늘은 알고리즘 포스팅이에요
재밌는 문제가 있길래 오랜만에!!!! 가져왔습니다

 

105번 문제이고 난이도는 Medium, 현재 Acceptance는 63.5%입니다

 

문제로 넘어갈게요

먼저 두 인티저 배열들인 preorder과 inorder이 주어집니다
preorder은 이진트리의 전위(preorder) 순회이고 inorder은 같은 트리의 중위(inorder) 순회래요
이 두 배열을 보고 우리는 이진트리를 생성하고 반환해야 해요

 

즉 인풋으로 preorder, inorder 배열들이 주어질 건데 이 정보를 가지고 이진트리를 만들어서 리턴해!

---

첫 번째 예제

두 번째 예제

제약들도 있으니 참고

---

자 이제 문제를 풀어봅시다

 

⭐️ 문제 풀기 전에 알아야 할 중요한 두 가지 사실이 있어요 ⭐️
1. preorder의 첫 번째 값은 항상 루트 값이다
2. inorder에서 preorder의 첫 번째 값이 있는 인덱스를 기준으로 왼쪽 자식, 오른쪽 자식이 나뉜다

 

1번 예제로 다시 가볼게요
실제로 input은 preorder, inorder배열만 주어지지만
이해를 위해서 왼쪽 실제 트리 모양도 같이 봐주세요!

preorder의 첫 번째 값은 루트 값이라고 했죠
그럼 preorder의 첫 번째 값인 3이 루트가 될 것이고
inoder에서 preorder의 루트 값이 있는 인덱스를 기준으로 왼쪽 오른쪽이 나뉜다고 했죠?
inorder [9, 3, 15, 20, 7]에서 3이 있는 곳의 인덱스는 1
그럼 인덱스 1 미만인 범위인 9는 루트의 왼쪽 부분이 되고 (하늘색)
1 이상의 범위인 15,20,7은 루트의 오른쪽 부분이 되겠죠 (핑크색)

 

LEVEL 1 완료

 

루트 3을 기준으로 왼쪽 부분을 볼게요 (하늘색)

3은 이미 진행했으니 엑스
preorder의 첫 번째 값은 루트 값이라고 했죠
그리고 inoder에서 preorder의 루트 값이 있는 인덱스를 기준으로 왼쪽 오른쪽이 나뉜다고 했죠?
하늘색 범위의 [9] 에서 9가 있는 곳은 인덱스는 0
그런데 하늘색 범위에는 9밖에 없으니 9에는 왼쪽, 오른쪽의 자식이 없네요!

 

왼쪽을 봤으니 이제 루트 3을 기준으로 오른쪽 부분을 볼게요 (핑크색)

3,9는 이미 진행했으니 엑스
preorder의 첫 번째 값은 루트 값이라고 했고
inoder에서 preorder의 루트 값이 있는 인덱스를 기준으로 왼쪽 오른쪽이 나뉜다고 했죠?
핑크색 범위 안 [15, 20, 7] 에서는 20의 인덱스는 1
그럼 인덱스 1 미만인 범위인 15는 루트의 왼쪽 부분이 될 것이고 (하늘색)
1 이상의 범위인 7은 루트의 오른쪽 부분이 될 것입니다 (핑크색)

 

LEVEL 2 완료

 

루트 20을 기준으로 왼쪽 부분을 볼게요 (하늘색)

하늘색 범위 [15] 에는 15밖에 없으니 15에는 왼쪽, 오른쪽의 자식이 없네요!

 

루트 20을 기준으로 오른쪽쪽 부분을 볼게요 (핑크색)

핑크색 범위 [7] 에서도 7밖에 없으니 7에는 왼쪽, 오른쪽의 자식이 없네요!

 

LEVEL 3 완료

 

위에서 말씀드렸던 것처럼 preorder의 첫 번째 값은 항상 루트 값이고
inorder에서 preorder의 첫 번째 값이 있는 인덱스를 기준으로 왼쪽, 오른쪽이 나뉘는 것을 활용해
recursive 이용해 이진트리를 만들 수 있었습니다

 

이걸 스위프트 코드로 작성하면?? 아래와 같습니다

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
    guard !inorder.isEmpty && !preorder.isEmpty else { return nil }
    
    let rootVal = preorder[0]
    var rootNode = TreeNode(rootVal)
    let mid = inorder.firstIndex(of: rootVal)!
    
    rootNode.left = buildTree(Array(preorder[1..<mid+1]), Array(inorder[...mid]))
    rootNode.right = buildTree(Array(preorder[(mid+1)...]), Array(inorder[(mid+1)...]))
    
    return rootNode
}

 

끝

 

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