LeetCode 双刀流：700. Search in a Binary Search Tree

700. Search in a Binary Search Tree

昨天提到链结串列（Linked List）的题目，今天就挑了一题「树（Tree）」的题目，还是经典的二元搜寻树（BST，Binary Search Tree）。二元搜寻树会根据资料数值加入的先後顺序与大小依序插入，小的往左边放、大的往右边放，最终形成一颗二元树，能够有效用於查询情境。对於一个二元搜寻树的「建立」、「新增」、「删除」或「查询」
都是基本的操作，不过当遇到复杂的树结构，就多了一层的挑战。

先看一下题目描述

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

再搭配范例理解题目

• Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

• Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

这个题目给一个 root，并且建构成一个二元树，要求从二元树中找到 val 的值，并且回传包含 val 作为 root 的子树。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：回圈迭代法

第一种方法就是直觉的利用二元搜寻树的特性一个一直找，目标值比较小就往左找、目标值比较小就往右找，直到找到该数值即回传。题目中要求「回传包含 val 作为 root 的子树」其实不用特别处理，因为树本身就是一个树状结构，只要专注找到数值就好。

那我们先用 Python 实作看看

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: 
        while root:
            if root.val == val:
                return root
            elif root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
        return root

也可以用 JavaScript 复刻一次

var searchBST = function(root, val) {
    while(root.val != null){
        if (root.val === val)
            return root
        else if (val < root.val)
            root = root.left
        else 
            root = root.right
    }
    return root
};

原本写法的条件判断比较复杂，可以利用三元运算的方式做简化：

# Python
while root:
  root = root.left if val < root.val else root.right
return root

# JavaScript
while(root !== null){
  root = val < root.val ? root.left : root.right;
}
return root

方法 ②：递回（recursion）

第二种方法是递回（recursion），概念是「判断这一层是否符合条件，否则就往两个子树各别往下层找」，然後直到找到为止直接回传。其实以树来说，递回的方法反而比较直觉，只要设定到起始与终止条件，设定就让递回自己依序完成。

那我们先用 Python 实作看看

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: return
        if root.val == val: return root
        return self.searchBST(root.left, val) or self.searchBST(root.right, val)

也可以用 JavaScript 复刻一次

var searchBST = function(root, val) {
    if(!root) return null
    if(root.val === val) return root
    return searchBST(root.left,val) || searchBST(root.right,val)
};

反思沉淀

从链结串列（Linked List）到树（Tree）或二元搜寻树（BST，Binary Search Tree），是一种从线性到非线性的概念。线性指的是只会有下一个可能，终究只会有一条路径；非线性的话则可能有不同的分岔，可能会产生出两条以上的可能路径。以二元树来说，每一个点最多可能会有两个点的下一个可能，因此可能就会有「不同往下找」的做法，应该先找完同一层的，还是先找到最底再回头找，就会有许多的变化可以玩。对於一个容器「建立」、「新增」、「删除」或「查询」都是基本的操作，不过当遇到复杂的链结串列或树结构，就多了一层的挑战。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 701. Insert into a Binary Search Tree

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。