給定一棵 BST 的根節點和一個要插入的值，將該值插入 BST 中並回傳根節點。保證插入的值在原樹中不存在。可以回傳任意一個合法的結果。
Example:
Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5]
Intuition
TIP
利用 BST 性質，比較值的大小決定往左或往右走，找到空位插入。
- BST 的插入永遠是在葉子節點的位置
- 比當前節點小往左走，比當前節點大往右走，直到找到 null 的位置
Approaches
⭐ 1. Recursive — O(h) / O(h)
- Idea: 遞迴比較值，找到 null 位置時建立新節點回傳
- Time:
O(h)，h 為樹高，平均 O(log n)，最差 O(n) - Space:
O(h)，遞迴堆疊深度
class Solution {
fun insertIntoBST(root: TreeNode?, `val`: Int): TreeNode? {
if (root == null) return TreeNode(`val`)
if (`val` < root.`val`) {
root.left = insertIntoBST(root.left, `val`)
} else {
root.right = insertIntoBST(root.right, `val`)
}
return root
}
}2. Iterative — O(h) / O(1)
- Idea: 迭代找到插入位置的父節點，直接掛上新節點
- Time:
O(h) - Space:
O(1)
class Solution {
fun insertIntoBST(root: TreeNode?, `val`: Int): TreeNode? {
val newNode = TreeNode(`val`)
if (root == null) return newNode
var curr = root
while (curr != null) {
if (`val` < curr.`val`) {
if (curr.left == null) {
curr.left = newNode
return root
}
curr = curr.left
} else {
if (curr.right == null) {
curr.right = newNode
return root
}
curr = curr.right
}
}
return root
}
}🔑 Takeaways
- Pattern: BST 的搜尋路徑 — 利用大小關係決定方向
- Key trick: BST 插入一定是在葉子位置，遞迴寫法中
root == null就是找到插入點的時機