700. 二叉搜索树中的搜索

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

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

示例 1:

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

Example 2:

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

提示：

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

题解：

思路一：借助队列广度优先遍历搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public TreeNode searchBST(TreeNode root, int val) {
    //据观察，此题应该广度优先遍历，找到目标节点，就将以该节点为根的子树返回
    Queue<TreeNode> que = new ArrayDeque<>();
    //根节点不为空，入队
    if(root != null){
        que.offer(root);
    }

    while(!que.isEmpty()){
        int size = que.size();
        TreeNode node = que.poll();
        if (node.val == val){
            return node;
        }
        if(node.left != null){
            que.offer(node.left);
        }
        if(node.right != null){
            que.offer(node.right);
        }

    }
    return null;
}

思路二：递归

根据二叉搜索数的特性来写递归

1
2
3
4
5
6
7
8
public TreeNode searchBST(TreeNode root, int val) {
    //递归出口
    if(root == null || root.val == val){
        return root;
    }
    //因为是二叉搜索数，所以右节点的值一定大于左节点，根据此特性可写出如下代码
    return val > root.val ? searchBST(root.right,val) : searchBST(root.left,val);
}

思路三：根据二叉搜索树的特性进行迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 public TreeNode searchBST(TreeNode root, int val) {
while(root != null){
         //目标节点在左子树,root指针指向左子树
         if(root.val > val){
             root = root.left;
         }else if(root.val < val){
             //目标节点在右子树，root指针指向右子树
             root = root.right;
         }else{
             //root为目标节点，直接返回
             return root;
         }
     }
     //没有找到，返回null
     return null;
 }