算法力扣刷题记录 五十三【700.二叉搜索树中的搜索】

前言

开始接触二叉搜索树。这是进入二叉搜索树的第一篇。
记录 五十三【700.二叉搜索树中的搜索】

---

一、题目阅读

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

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

示例 1:

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

示例 2:

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

提示：

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

---

二、尝试实现

思路

1. 题目说二叉搜索树：左孩子 < 中间节点 < 右孩子。那么类似二分搜索，因为顺序已经排好，那么根据大小进入到左子树或右子树中去继续找。
2. 终止条件：节点为空，说明不存在，return nullptr；
3. 逻辑：

• 节点值相等，直接return；
• 节点值小，递归右子树；
• 节点值大，递归左子树。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root){//是否是空节点
            return nullptr;
        }
        //遍历
        if(root->val == val){
            return root;
        }else if(root->val < val){
            return searchBST(root->right,val);
        }else if(root->val > val){
            return searchBST(root->left,val);
        }
        return nullptr;//默认。合理不会走到这
    }
};
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

---

三、参考学习

参考学习链接

学习内容

1. 二叉搜索树：任意节点作为子树的根节点，左子树所有数值都比该节点小；右子树所有数值都比该节点大。这提供了搜索的方向 。
2. 递归法：二、中的实现也是递归法。那么改进之处：

• 空节点和相等时，可以合并成return root。同时作为终止条件。

• 先定义result = nullptr接收返回值。

• 递归另一种代码实现：

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   * };
   */
  class Solution {
  public:
      TreeNode* searchBST(TreeNode* root, int val) {
          if(!root || root->val == val){//是否是空节点
              return root;
          }
          TreeNode* result = nullptr;
          if(root->val < val){
              result= searchBST(root->right,val);
          }else if(root->val > val){
              result =  searchBST(root->left,val);
          }
          return result;
      }
  };
  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

3. 迭代法：思路肯定一样。本题好处：二叉搜索树给了下一步的走向，往左子树走还是往右子树走。

4. 迭代法代码实现：

   /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
   class Solution {
   public:
       TreeNode* searchBST(TreeNode* root, int val) {
           TreeNode* cur = root;
           while(cur){
               if(cur->val == val) return cur;
               else if(cur->val > val) cur = cur->left;
               else if(cur->val < val) cur = cur->right;
           }
           return nullptr;
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23

   对比参考代码：一样。

---

总结

【700.二叉搜索树中的搜索】

（欢迎指正，转载标明出处）