# [LeetCode 700] 这就是二叉搜索树的神奇之处了

其实在二叉树里搜索值,都可以用通用的树遍历模板。比如,以中序迭代遍历为例:

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  const stack: TreeNode[] = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop()!;
    if (root.val === val) return root;
    root = root.right;
  }
  return null;
}

但是因为二叉搜索树的性质,左子树小右子树大,就可以用类似于二分搜索的思路去做:

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  while (root) {
    if (root.val === val) return root;
    else root = root.val > val ? root.left : root.right;
  }
  return null;
}
最后更新于: 6/25/2020, 2:10:06 PM