在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习! 下面我们仍然通过例题进行讲解。
第700题:二叉搜索树中的搜索 |
---|
给定二叉搜索树(BST)的根节点和一个值。你需要在 BST 中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL 。 |
示例:
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中,如果要找的值是 5 ,但因为没有节点值为 5 ,我们应该返回 NULL 。
本题为必须掌握! 需要非常熟悉 为后续题目打基础!
先复习一下,二叉搜索树(BST)的特性:
如下图就是一棵典型的BST:
假设目标值为 val,根据BST的特性,我们可以很容易想到查找过程
很简单,不是吗?
给出递归和迭代两种解法:
//递归
public TreeNode searchBST(TreeNode root, int val) {
if (root == null)
return null;
if (root.val > val) {
return searchBST(root.left, val);
} else if (root.val < val) {
return searchBST(root.right, val);
} else {
return root;
}
}
//迭代
public TreeNode searchBST(TreeNode root, int val) {
while (root != null) {
if (root.val == val) {
return root;
} else if (root.val > val) {
root = root.left;
} else {
root = root.right;
}
}
return null;
}
递归与迭代的区别 递归:重复调用函数自身实现循环称为递归; 迭代:利用变量的原值推出新值称为迭代,或者说迭代是函数内某段代码实现循环;