LeetCode_68_SearchInABinarySearchTree


1. question: 二叉搜索树中的搜索(简单)

给定二叉搜索树(BST)的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-in-a-binary-search-tree

示例 1:

示例1

1
2
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]

Example 2:

示例2

1
2
输入:root = [4,2,7,1,3], val = 5
输出:[]

提示:

1
2
3
4
数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

2. answers

这道题还是比较简答的。注意二叉搜索树的性质即可,和二分查找类似。递归的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution_0067 {

public static TreeNode searchBST(TreeNode root, int val) {

if(root == null) return null;

if(root.val > val) return searchBST(root.left, val);

if(root.val < val) return searchBST(root.right, val);

return root;

}

public static void main(String[] args) {
System.out.println();


TreeNode tn5 = new TreeNode(3);
TreeNode tn4 = new TreeNode(1);
TreeNode tn3 = new TreeNode(2, tn4, tn5);
TreeNode tn2 = new TreeNode(7);
TreeNode tn1 = new TreeNode(4, tn3, tn2);

TreeNode result = searchBST(tn1, 5);

Queue<TreeNode> queue = new LinkedList<>();

if(result == null) return;

queue.offer(result);

while(queue.size() > 0) {

int length = queue.size();

while(length-- > 0) {

result = queue.poll();

System.out.print(result.val + "\t");

if(result.left != null) queue.offer(result.left);
if(result.right != null) queue.offer(result.right);

}

System.out.println();
}
}
}

迭代的代码如下所示:

1
2
3
4
5
6
7
8
9
10
public static TreeNode searchBST(TreeNode root, int val) {

while(root != null) {
if(root.val > val) root = root.left;
else if(root.val < val) root = root.right;
else return root;
}

return null;
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录