題目網址：https://leetcode.cn/problems/insert-into-a-binary-search-tree/

題意：給一 BST 的 root 和要插入的值 val, 返回插入後 BST 的 root, BST 中所有的 node.val 皆為獨一無二的。

注意：可能存在多種有效的插入方式, 返回任意一種即可。

Solution 1：

想法：利用 DFS

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }

        if (val > root->val) {
            root->right = insertIntoBST(root->right, val);
        } else {
            root->left = insertIntoBST(root->left, val);
        }

        return root;
    }
};
  • time：$O(n)$ ➔ worse case：遍歷 BST
  • space：$O(n)$ ➔ 取決於遞迴深度, worse case：skew tree

Solution 2：

想法：同 Solution 1, 從 recursive 改成 iterative

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }

        TreeNode *cur = root;
        while (cur) {
            if (val > cur->val) {
                // 往右子樹尋找, 一旦為 null 則插入 val
                if (!cur->right) {
                    cur->right = new TreeNode(val);
                    break;
                } else {
                    cur = cur->right;
                }
            } else {
                // 往左子樹尋找, 一旦為 null 則插入 val
                if (!cur->left) {
                    cur->left = new TreeNode(val);
                    break;
                } else {
                    cur = cur->left;
                }
            }
        }

        return root;
    }
};
  • time：$O(n)$ ➔ worse case：遍歷 BST
  • space：$O(1)$ ➔ 只需常數空間