0700. Search in a Binary Search Tree (Easy)
Question
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.
For example,
| |
| |
You should return this subtree:
| |
In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.
分析/解題
給定一個二元搜尋樹及一個值，試找到這個樹上含有該值的節點；
如果找不到任何節點的值和此值相等的話，回傳NULL。
一個Binary Search Tree在進行搜尋特定值上最大的好處就是，
**碰到相等是目標，比完較小往左走，
比完較大往右走，走到盡頭就沒有。(XDDDD)**類似binary search，只是我們的每次切半/改動上下界的操作，
更改為往左走或往右走。
所以我們只要進行遞迴，直到走到NULL(NIL)或走到剛好對的值即可，
下面的程式碼中，由於判斷root是否為NIL 及root的值等於目標值 的狀況，
均為回傳root (雖然一種情況是NIL，另一種情況不是)，
所以我們可以將之合併。
而當val < root.val 的時候，
選擇往左走 去找比當下的root更小的值 來比較，反之則往右走。
在實測上以筆者目前的觀察，是否全數使用if/elif連貫的判斷式，
或者前面root的回傳是否合併成一個情況，
均對執行的速度沒有特別明顯的影響 ，
故讀者可依自己的喜好選擇撰寫的方式，只需邏輯正確即可。
此外，之前可能有提到過的三元運算子 ( ? : )也僅是方便縮短行數，
同樣對結果沒有影響。
Java
Python
如果讀者習慣於使用LeetCode解二元樹或二元搜尋樹的題目，
應該會發現其實二元搜尋樹是可以使用陣列/串列的方式進行輸入 的。
這麼做的好處是只要管理好index，就可以用index的操作 來達到走訪某個節點的目的，而不用真的去把每個節點都進行連結到left/right。
缺點的部分則是有些地方必須輸入null進去(因為有可能會是null節點)。
讀者可以找一些題目來思考一下，
(像是前面的0094. Binary Tree Inorder Traversal)
如果從index i想要走到其left/right節點，這兩個的節點index會是多少呢？
讀者可以開啟Testcase中的Tree Visualizer，
來觀看輸入的陣列會長成的樹的形狀。
(註：這種表示法未必是通用的，但可以做為參考。)
面試實際可能會遇到的問題
「時間/空間複雜度？」
(Worst case O(N)/Average Case O(logN) , O(1)，
最糟的狀況是所有節點集中在同一側，一路搜尋到最底下；
平均來說，如果節點較接近平衡的分布的話，
每次搜尋往下走能去掉一半的可能性，所以會是O(logN)。
由於不需要額外的紀錄，所以空間複雜度為O(1))
相似及延伸
1.0701. Insert into a Binary Search Tree
Special Thanks suggestions/corrections from viewers: 感謝Tony Kuo 的建議，這邊附上之前講的BST定義及validation的文章。
從LeetCode學演算法 — 16 BST (1) (0098. Validate Binary Search Tree)
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~