forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEcoFriendlyAppleSu.kt
More file actions
36 lines (30 loc) ยท 1.02 KB
/
EcoFriendlyAppleSu.kt
File metadata and controls
36 lines (30 loc) ยท 1.02 KB
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
32
33
34
35
36
package leetcode_study
/*
* binary tree ์ข์ฐ ๋ฒ๊ฒฝ ๋ฌธ์
* ์ฌ๊ท๋ฅผ ํตํด ๋ฌธ์ ํด๊ฒฐ
* ์๊ฐ ๋ณต์ก๋: O(n)
* -> n๊ฐ์ ๋
ธ๋๋ฅผ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธ
* ๊ณต๊ฐ ๋ณต์ก๋: O(n) ํน์ O(log n)
* -> ์ฌ๊ท ์ฌ์ฉ ์ ์คํ์ ์์
* -> ๊ท ํ์กํ binary tree์ ๊ฒฝ์ฐ O(log n)์ ๊ณต๊ฐ์ด ํ์ํ๊ณ ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ(์ต์
์ ๊ฒฝ์ฐ) O(n)์ ๊ณต๊ฐ ๋ณต์ก๋ ์๊ตฌ
* */
fun invertTree(root: TreeNode?): TreeNode? {
recursiveNode(root)
return root
}
fun recursiveNode(parentNode: TreeNode?) {
if (parentNode == null) return
swapNode(parentNode) // ํ์ฌ ๋
ธ๋์ left์ right๋ฅผ ๊ตํ
recursiveNode(parentNode.left) // ์ผ์ชฝ ์๋ธํธ๋ฆฌ ํ์
recursiveNode(parentNode.right) // ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ ํ์
}
fun swapNode(parentNode: TreeNode?) {
if (parentNode == null) return
val temp = parentNode.left
parentNode.left = parentNode.right
parentNode.right = temp
}
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}