701. Insert into a Binary Search Tree

Medium

Description

給定一棵 BST 的根節點和一個要插入的值，將該值插入 BST 中並回傳根節點。保證插入的值在原樹中不存在。可以回傳任意一個合法的結果。

Example:

Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5]

Intuition#

利用 BST 性質，比較值的大小決定往左或往右走，找到空位插入。

BST 的插入永遠是在葉子節點的位置
比當前節點小往左走，比當前節點大往右走，直到找到 null 的位置

Approaches#

⭐ 1: Recursive#

概念: 遞迴比較值，找到 null 位置時建立新節點回傳
時間複雜度: O(h)，h 為樹高，平均 O(log n)，最差 O(n)
空間複雜度: 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)

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 的搜尋路徑 — 利用大小關係決定方向
關鍵技巧: BST 插入一定是在葉子位置，遞迴寫法中 root == null 就是找到插入點的時機