二叉樹：二叉搜尋樹登場！

用好二叉搜尋樹的特性，就發現周遊都簡單了 ❞

700.二叉搜尋樹中的搜尋

給定二叉搜尋樹（BST）的根節點和一個值。你需要在BST中找到節點值等于給定值的節點。傳回以該節點為根的子樹。如果節點不存在，則傳回 NULL。

例如，

在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該傳回 NULL。

思路

之前我們講了都是普通二叉樹，那麼接下來看看二叉搜尋樹。

在關于二叉樹，你該了解這些！中，我們已經講過了二叉搜尋樹。

二叉搜尋樹是一個有序樹：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

它的左、右子樹也分别為二叉搜尋樹

這就決定了，二叉搜尋樹，遞歸周遊和疊代周遊和普通二叉樹都不一樣。

本題，其實就是在二叉搜尋樹中搜尋一個節點。那麼我們來看看應該如何周遊。

确定遞歸函數的參數和傳回值

遞歸函數的參數傳入的就是根節點和要搜尋的數值，傳回的就是以這個搜尋數值所在的節點。

代碼如下：

确定終止條件

如果root為空，或者找到這個數值了，就傳回root節點。

确定單層遞歸的邏輯

看看二叉搜尋樹的單層遞歸邏輯有何不同。

因為二叉搜尋樹的節點是有序的，是以可以有方向的去搜尋。

如果root->val > val，搜尋左子樹，如果root->val < val，就搜尋右子樹，最後如果都沒有搜尋到，就傳回NULL。

這裡可能會疑惑，在遞歸周遊的時候，什麼時候直接return 遞歸函數的傳回值，什麼時候不用加這個 return呢。

我們在二叉樹：遞歸函數究竟什麼時候需要傳回值，什麼時候不要傳回值？中講了，如果要搜尋一條邊，遞歸函數就要加傳回值，這裡也是一樣的道理。

「因為搜尋到目标節點了，就要立即return了，這樣才是找到節點就傳回（搜尋某一條邊），如果不加return，就是周遊整棵樹了。」

整體代碼如下：

一提到二叉樹周遊的疊代法，可能立刻想起使用棧來模拟深度周遊，使用隊列來模拟廣度周遊。

對于二叉搜尋樹可就不一樣了，因為二叉搜尋樹的特殊性，也就是節點的有序性，可以不使用輔助棧或者隊列就可以寫出疊代法。

對于一般二叉樹，遞歸過程中還有回溯的過程，例如走一個左方向的分支走到頭了，那麼要調頭，在走右分支。

而「對于二叉搜尋樹，不需要回溯的過程，因為節點的有序性就幫我們确定了搜尋的方向。」

例如要搜尋元素為3的節點，「我們不需要搜尋其他節點，也不需要做回溯，查找的路徑已經規劃好了。」

中間節點如果大于3就向左走，如果小于3就向右走，如圖：

二叉搜尋樹

是以疊代法代碼如下：

第一次看到了如此簡單的疊代法，是不是感動的痛哭流涕，哭一會~

總結

本篇我們介紹了二叉搜尋樹的周遊方式，因為二叉搜尋樹的有序性，周遊的時候要比普通二叉樹簡單很多。

但是一些同學很容易忽略二叉搜尋樹的特性，是以寫出周遊的代碼就未必真的簡單了。

是以針對二叉搜尋樹的題目，一樣要利用其特性。

文中我依然給出遞歸和疊代兩種方式，可以看出寫法都非常簡單，就是利用了二叉搜尋樹有序的特點。