二叉搜索树中的搜索

题目：

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

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

思路1：

使用递归遍历，若节点的值大于val，则判断右子树；若节点的值小于val，则判断左子树；等于的话，就返回该节点。

方法：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(NULL == root) return NULL;
        if(root->val == val) return root;
        else if(root->val > val)  return searchBST(root->left, val);
        else  return searchBST(root->right, val);
    }
};

思路2：

使用迭代遍历，根据二叉搜索树的特殊性，可以不适用栈来模拟深度遍历，到达空节点就结束。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* node = root;
        while(node != NULL)
        {
            if(node->val < val)
            {
                node = node->right; 
            }
            else if(node->val > val)
            {
                node = node->left; 
            }
            else
            {
                return node;
            }
        }
        return NULL;
    }
};