解題說明
Insert into a Binary Search Tree
題目描述:給定一棵二元搜尋樹(BST)的根節點和一個要插入的值 val(保證不存在於樹中),將該值插入 BST 中並回傳更新後的根節點。插入方式不唯一,只要結果仍是有效的 BST 即可。
解題思路:利用 BST 的性質,從根節點開始比較:
- 若
val小於當前節點值,往左子樹走。 - 若
val大於當前節點值,往右子樹走。 - 當到達空節點時,建立新節點並回傳。
遞迴法最為簡潔:每次遞迴呼叫會回傳子樹的根,走到空位時回傳新節點,自然地連接到父節點上。
C++ 解法
複雜度分析
時間複雜度:O(h) — h 為樹的高度,平衡樹為 O(log n),退化樹為 O(n)。
空間複雜度:O(h) — 遞迴堆疊深度等於樹的高度。
虛擬碼
1. If root is null, return new TreeNode(val) 2. If val < root.val: a. root.left = insertIntoBST(root.left, val) 3. Else: a. root.right = insertIntoBST(root.right, val) 4. Return root
其他解法
迭代法:用一個指標從根節點走到正確的空位,記錄父節點,最後將新節點連接到父節點的左或右。時間 O(h),空間 O(1)。迭代法不需要遞迴堆疊,適合極深的樹。
注意:題目只要求插入到葉節點位置。若要維持平衡(如 AVL 樹),插入後還需要旋轉操作,但本題不要求。
延伸思考
- 如果要在插入後保持樹的平衡(如 AVL 樹),需要額外做什麼?
- 如果允許重複值,BST 的插入規則應如何調整?
- 迭代法與遞迴法在實際效能上的差異是什麼?