二叉搜索树中的搜索 (opens new window)

• 难度：Easy
• 标签：递归

刷题思路

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

方法 1 递归

• 复杂度：
  • 时间 O(logn)
  • 空间 O(logn). 递归调用栈消耗

var searchBST = function(root, val) {
    if (!root) return null
    if (root.val === val) return root
    return searchBST(root.val > val ? root.left: root.right, val)
};

方法 2 迭代

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

var searchBST = function(root, val) {
    while (root) {
        if (root.val === val) return root
        root = val < root.val ? root.left : root.right
    }
    return null
};

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