问题

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4102 访问。

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

给定二叉搜索树:

4

       / \

      2   7

     / \

    1   3

和值: 2

你应该返回如下子树:

2     

     / \   

    1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

---

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

Given the tree:

        4

       / \

      2   7

     / \

    1   3

And the value to search: 2

You should return this subtree:

2     

     / \   

    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

---

示例

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4102 访问。

public class Program {

    public static void Main(string[] args) {
        var root = new TreeNode(1) {
            left = new TreeNode(3) {
                left = new TreeNode(5),
                right = new TreeNode(7)
            },
            right = new TreeNode(9)
        };

        var res = SearchBST(root, 5);
        ShowTree(res);
        Console.WriteLine();

        res = SearchBST2(root, 6);
        ShowTree(res);

        Console.ReadKey();
    }

    public static void ShowTree(TreeNode node) {
        if(node == null) {
            Console.Write("null ");
            return;
        }
        Console.Write($"{node.val} ");
        ShowTree(node.left);
        ShowTree(node.right);
    }

    public static TreeNode SearchBST(TreeNode root, int val) {
        if(root == null) return null;
        if(root.val == val) return root;
        var left = SearchBST(root?.left, val);
        if(left != null) return left;
        var right = SearchBST(root?.right, val);
        if(right != null) return right;
        return null;
    }

    public static TreeNode SearchBST2(TreeNode root, int val) {
        if(root == null) return null;
        if(val > root.val) return SearchBST2(root.right, val);
        if(val < root.val) return SearchBST2(root.left, val);
        return root;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4102 访问。

5 null null
null

---

分析：

显而易见，以上2种算法的时间复杂度均为：  。