問題描述
給
定
二叉搜尋樹
（BST）的根節點和一個值。你需要在BST中找到節點值等於給定值的節點。返回以該節點為根的子樹。如果節點不存在，則返回 NULL。
示例 1:
輸入：root = ［4，2，7，1，3］， val = 2
輸出：［2，1，3］
示例 2:
輸入：root = ［4，2，7，1，3］， val = 5
輸出：［］
提示：
數中節點數在［1， 5000］範圍內
1 <= Node。val <= 10^7
root 是二叉搜尋樹
1 <= val <= 10^7
問題分析
這題說的是在
二叉搜尋樹
中的查詢，我們首先要搞懂什麼是二叉搜尋樹。維基百科上對二叉搜尋樹是這樣描述的：
二叉查詢樹（英語：Binary Search Tree），也稱為二叉查詢樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
若任意節點的左子樹不空，則
左子樹上所有節點的值均小於它的根節點的值
；
若任意節點的右子樹不空，則
右子樹上所有節點的值均大於它的根節點的值
；
任意節點的左、右子樹也分別為二叉查詢樹
；
二叉查詢樹相比於其他資料結構的優勢在於查詢、插入的時間複雜度較低。為O（log n）。
一句話概括就是
二叉搜尋樹每個節點的值都比他的所有左子節點值大，並且比他的所有右子節點值小
。
所以這題查詢的時候從根節點開始，如果找到就返回，如果比根節點小就往左子節點查詢，否則就往右子節點查詢……
public TreeNode searchBST（TreeNode root， int val） { //如果節點為空就返回空，或者找到了要找的節點也直接返回 if （root == null || root。val == val） return root； //如果val比當前節點的值小就在當前節點的左子節點來找， //否則就在當前節點的右子節點來找 if （val < root。val） return searchBST（root。left， val）； else return searchBST（root。right， val）；}
程式碼比較簡單，我們還可以改為非遞迴的方式
public TreeNode searchBST（TreeNode root， int val） { //如果當前節點不為空，並且也不是我們要找的，就繼續查詢 while （root ！= null && root。val ！= val） root = val < root。val ？ root。left ： root。right； return root；}
