700. 二叉搜索树中的搜索

1.题目

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

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

2.示例

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

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

3.答案

这里返回的是以该节点为根的子树，那就是返回一个节点。

二叉搜索树：递归地满足左子树上的值小于根节点的值，右孩子上的值大于根节点上的值的二叉树。
所以在二叉树上搜索target，根节点为target直接返回，根节点小于target则在根的右子树上继续搜索，否则在根的左子树搜索。

①递归

 TreeNode* searchBST(TreeNode* root, int val) {

        //利用二叉搜索树的特性，递归查找
        if(!root) return root;
        if(root->val==val) return root;  //就是此节点
        if(root->val<val) return searchBST(root->right,val);   // 根的值小，所以向右孩子上查找
         return searchBST(root->left,val);   //根的值大，所以向左孩子上查找
    }
1
2
3
4
5
6
7
8

②简单迭代

由于二叉树的特性，一路向下查找搜索不需要返回查找之类的。

   TreeNode* searchBST(TreeNode* root, int val) {
      while(root){  //节点非空
          if(root->val>val) root=root->left;
          else if(root->val<val) root=root->right;
          else return root;
      }
      return nullptr;
    }
1
2
3
4
5
6
7
8

③DFS

TreeNode* searchBST(TreeNode* root, int val) {
       // 迭代进行
       if(!root) return root;
       stack<TreeNode*> st;
       st.push(root);
       while(!st.empty()){
           TreeNode*tmp=st.top();
           st.pop();
           if(tmp->val==val) return tmp;
            else if(tmp->val<val&&tmp->right) st.push(tmp->right);  //直接右孩子上进行查找
            else if(tmp->left) st.push(tmp->left);  //左孩子上查找
       }
       return nullptr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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