递归
解题思路
二叉搜索树的 左子树所有节点的元素值均小于根的元素值，右子树所有节点的元素值均大于根的元素值；
据此可以得到如下算法：
- 若 root 为空则返回空节点；
- 若
val == root.val，则返回 root；- 若
val < root.val，需要递归左子树，继续向寻找；- 若
val > root.val，需要递归右子树，继续向右寻找；
复杂度
-
时间复杂度：
O(N)，其中 N 是二叉搜索树的节点数，最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下需要递归 N 次； -
空间复杂度：
O(N)，最坏情况下递归需要O(N)的栈空间；
代码实现
var searchBST = function (root, val) {
if (root === null) return root;
if (root.val === val) return root;
if (root.val > val) return searchBST(root.left, val);
if (root.val < val) return searchBST(root.right, val);
};
迭代
复杂度
-
时间复杂度：
O(N)，其中 N 是二叉搜索树的节点数，最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下需要迭代 N 次； -
空间复杂度：
O(N)，最坏情况下递归需要O(N)的栈空间；
代码实现：
var searchBST = function (root, val) {
while (root) {
if (val === root.val) {
return root;
}
root = val < root.val ? root.left : root.right;
}
return null;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 739. 每日温度
上一篇
评论
