700. 二叉搜索树中的搜索

;(function () {
  /**
   * 700. 二叉搜索树中的搜索
   * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
   * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
   *
   * 输入：root = [4,2,7,1,3], val = 2
   * 输出：[2,1,3]
   *
   * 输入：root = [4,2,7,1,3], val = 5
   * 输出：[]
   *
   * 备注：
   * 二叉搜索树满足如下性质：
   * === 左子树所有节点的元素值均小于根的元素值；
   * === 右子树所有节点的元素值均大于根的元素值。
   *
   */
  class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
      this.val = val === undefined ? 0 : val
      this.left = left === undefined ? null : left
      this.right = right === undefined ? null : right
    }
  }

  function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    // 方法一：
    // let res: TreeNode | null = null
    // function preorder (root: TreeNode | null) {
    //     if (!root) return
    //     // 如果节点值找到了
    //     if (root.val === val) {
    //         res = root
    //         return
    //     }
    //     preorder(root.left)
    //     preorder(root.right)
    // }
    // preorder(root)
    // return res

    // 方法二：优化方法一
    let res: TreeNode | null = null
    function preorder(root: TreeNode | null) {
      if (!root) return
      // 如果节点值找到了
      if (root.val === val) {
        res = root
        return
      }
      // 根据【备注】二叉搜索树满足的性质
      root.val > val ? preorder(root.left) : preorder(root.right)
    }
    preorder(root)
    return res
  }
})()