二叉搜索树中的插入操作 (opens new window)

• 难度：Medium
• 标签：递归

刷题思路

• [x] 递归
• [x] 迭代

方法 1 递归

• 复杂度：
  • 时间 O(logn)
  • 空间 O(logn)

var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val)
    if (val < root.val) root.left = insertIntoBST(root.left, val)
    if (val > root.val) root.right = insertIntoBST(root.right, val)
    return root
};

方法 2 迭代

• 复杂度：
  • 时间 O(logn)
  • 空间 O(1)

var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val)
    let curr = root
    while (curr) {
        if (val < curr.val) {
            if (curr.left) {
                curr = curr.left
            } else {
                curr.left = new TreeNode(val)
                break
            }
        }
        if (val > curr.val) {
            if (curr.right) {
                curr = curr.right
            } else {
                curr.right = new TreeNode(val)
                break
            }
        }
    }
    return root
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~