일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- objc
- ios
- SWIFT
- rxswift
- 알고리즘
- 독서
- swift5
- 스위프트UI
- Animation
- 딥러닝
- swiftUI
- string
- Deep learning
- ARC
- iOS SwiftUI
- 문자열
- 스위프트
- wwdc
- stanford SwiftUI
- RX
- Xcode
- 머신러닝
- Algorithm
- 애니메이션
- ReactiveX
- 책 후기
- 책
- leetcode
- objective-c
- 책 추천
- Today
- Total
THIS IS ELLIE
LeetCode 알고리즘 Construct Binary Tree from Preorder and Inorder Traversal 본문
LeetCode 알고리즘 Construct Binary Tree from Preorder and Inorder Traversal
Ellie Kim 2024. 2. 25. 20:40안녕하세요 :) 오늘은 알고리즘 포스팅이에요
재밌는 문제가 있길래 오랜만에!!!! 가져왔습니다
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/
'공부 > Algorithm' 카테고리의 다른 글
LeetCode 알고리즘 Sum of Two Integers (0) | 2022.09.15 |
---|---|
LeetCode 알고리즘 Pascal's Triangle (0) | 2022.04.21 |
LeetCode알고리즘 Container With Most Water (2) | 2022.04.10 |
트라이(trie) 알고리즘 (0) | 2022.03.01 |
LeetCode알고리즘 Maximum Matrix Sum (3) | 2022.02.13 |