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

解题思路：递归解决

递归结束条件：传入结点为NULL

1. 判断当前结点的值与根结点的值是否相等，若相等返回当前结点的值
2. 若不相等，判断是大于还是小于当前结点的值，如果大于，进入右子树，如果小于进入左子树

struct TreeNode* searchBST(struct TreeNode* root, int val){
    // 递归结束条件：传入结点为NULL
    if(!root)
        return NULL;
    // 1.判断当前结点的值与根结点的值是否相等，若相等返回当前结点的值
    if(root->val == val)
        return root;
    // 2.若不相等，判断是大于还是小于当前结点的值，如果大于，进入右子树，如果小于进入左子树
    if(root->val < val)
        return searchBST(root->right, val);
    else
        return searchBST(root->left, val);
}

思路二：迭代法解决

//迭代法
struct TreeNode* searchBST(struct 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 NULL;
}