lc.700 二叉搜索树中的搜索

题目要求

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

方法1：递归

二叉搜索树的性质

左子树所有节点的元素值均小于根的元素值；
右子树所有节点的元素值均大于根的元素值。

算法

若 root 为空则返回空节点；
若 val=root.val，则返回 root；
若 val<root.val，递归左子树；
若 val>root.val，递归右子树。

class Solution {
public:
    TreeNode *searchBST(TreeNode *root, int val) {
        if (root ** nullptr) {
            return nullptr;
        }
        if (val ** root->val) {
            return root;
        }
        return searchBST(val < root->val ? root->left : root->right, val);
    }
};

方法2：层序

层序遍历整个树，先在最开始创建一个结点p初始化为null，如果遍历到值等于目标值的结点，就令p等于该结点，最后返回p（如果不存在目标结点，就会返回p的初始化值null）