解題說明
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 的插入規則應如何調整？
- 迭代法與遞迴法在實際效能上的差異是什麼？