Day49 代码随想录打卡|二叉树篇---二叉搜索树中的搜索

题目（leecode T700）：

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

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

方法：

递归法：本题考察了二叉搜索树的特性，二叉搜索树指的是在这个二叉树中，他的每一个根节点的值都大于他的左子树的值同时都小于他的右子树的值。这个特性对于我们查找某个节点就非常的容易，大了往左找，小了往右找即可。分析递归的三要素：

1.传入参数和返回值：这里需要传入的是二叉树的节点指针和我们需要搜索的值val

2：终止条件：根据二叉搜索树的处理逻辑，当我们遍历到空节点时，就说明这个树中没有我们需要查找的节点，当我们正好找到节点值等于val值时就说明有我们需要找的树

3：单层处理逻辑：本题的单层处理逻辑很简单，就是我们刚才分析的，如果当前root->val值大于我们需要找的val，那我们就往当前节点的左子树递归；反之往右子树递归。

题解：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == NULL || root->val == val) return root;            //终止条件
        TreeNode* result = NULL;
        if(root->val > val) result = searchBST(root->left, val);     //大了往左找
        if(root->val < val) result = searchBST(root->right, val);    //小了往右找
        return result;
    }
};

迭代法：
由于二叉搜索树特殊的特性，使得其使用迭代法也非常的简单。因为我们不需要回溯，每一步都是根据特性往下遍历的，大了往左，小了往右，直到找到了符合条件的节点就返回

题解：
 

class Solution {
public:
    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;
    }
};