C++算法练习-day41——700二叉搜索树中的搜索

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：给定一个二叉搜索树（BST）的根节点 root 和一个值 val，请在该二叉搜索树中查找值等于 val 的节点，并返回该节点的指针。如果不存在这样的节点，则返回 nullptr。

思路：

1. 二叉搜索树性质：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，且小于其右子树中所有节点的值。

2. 递归搜索：利用二叉搜索树的性质，我们可以使用递归的方法进行搜索。从根节点开始，如果目标值大于当前节点的值，则递归地在右子树中搜索；如果目标值小于当前节点的值，则递归地在左子树中搜索；如果目标值等于当前节点的值，则返回当前节点的指针。

3. 终止条件：递归的终止条件是遇到空节点（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) {  
        // 如果当前节点为空，表示已经遍历到叶子节点的下一个空位置，返回 nullptr  
        if(!root){  
            return nullptr;  
        }  
          
        // 如果目标值大于当前节点的值，递归地在右子树中搜索  
        if(val > root->val){  
            return searchBST(root->right, val);  
        }  
          
        // 如果目标值小于当前节点的值，递归地在左子树中搜索  
        else if(val < root->val){  
            return searchBST(root->left, val);  
        }  
          
        // 如果目标值等于当前节点的值，返回当前节点的指针  
        else{  
            return root;  
        }  
    }  
};

/*简洁一些写的话可以这样*/
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root||root->val==val){
            return root;
        }
        return searchBST(val>root->val?root->right:root->left,val);
    }
};

知识点摘要

1. 二叉搜索树（BST）：一种特殊的二叉树，满足每个节点的值都大于其左子树中所有节点的值，且小于其右子树中所有节点的值。

2. 递归搜索：在数据结构中，递归是一种常用的搜索算法，特别适用于树和图等递归结构。

3. 终止条件：在递归函数中，必须有一个明确的终止条件来防止无限递归。

通过这道题目，我们学习了如何在二叉搜索树中使用递归方法进行搜索。二叉搜索树的性质使得我们可以高效地定位目标值，而递归方法则提供了一种简洁而直观的解决方案。在实际应用中，二叉搜索树和递归搜索都是非常重要的数据结构和算法，它们不仅适用于单独的搜索问题，还可以作为更复杂算法的基础。通过不断练习和深入理解这些基础知识和技巧，我们可以更好地解决各种实际问题。