LeetCode演算法題-Search in a Binary Search Tree（Java實現）
這是悅樂書的第295 次更新，第314 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第163題（順位題號是700）。給定一個二叉搜尋樹（BST）的和正整數val。 你需要在BST中找到節點的值等於給定val的節點。返回以該節點為根的子樹。如果此節點不存在，則應返回null。例如：
鑑於樹：
4 / \ 27 / \ 13
以及搜尋的價值val：2
你應該返回這個子樹：
2 / \ 13
在上面的示例中，如果我們要搜尋值5，因為沒有值為5的節點，我們應該返回null。
注意：空樹由null表示，因此你可以將預期輸出（序列化樹格式）視為[]，而不是null。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
直接使用遞迴。因為題目給的二叉樹是BST，其中序遍歷的節點值是從小到大排列且有序的，因此，直接使用中序遍歷的順序，按照左子樹-->根-->右子樹的順序遍歷即可。
// 藉助中序遍歷，左根右的順序
public TreeNode searchBST(TreeNode root, int val) {
// 先判空
if (root == null) {
return null;
}
// 如果val大於當前節點值，就往右子樹裡面找
if (root.val < val) {
return searchBST(root.right, val);
}
// 如果相等，返回當前以節點為根節點的子樹
if (root.val == val) {
return root;
}
// 如果val小於當前節點值，就往左子樹裡面找
if (root.val > val) {
return searchBST(root.left, val);
}
return null;
}
03 第二種解法
也可以世界使用迭代的方式，藉助while迴圈來實現，迴圈內部的判斷邏輯和第一種解法類似，如果當前節點值大於val，就進入左子樹找；如果當前節點值小於val，就進入右子樹找；如果相等，直接返回以當前節點為根節點的子樹。
public TreeNode searchBST(TreeNode root, int val) {
while (root != null) {
if (root.val > val) {
root = root.left;
} else if(root.val < val){
root = root.right;
} else {
return root;
}
}
return null;
}
04 第三種解法
我們也可以使用佇列來做。將所有節點值依次入佇列，在入佇列前先判斷節點值是否等於val，等於就直接返回當前節點所在子樹。
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
if (temp.val == val) {
return temp;
}
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
return null;
}
05 第四種解法
我們也可以將第三種方法再優化，不必所有的節點都進佇列，根據節點值的大小，來判斷是進左子樹還是進右子樹，此解法與第二種解法類似，但是使用佇列會有點多餘，直接使用第二種解法會更好，第二種解法的空間複雜度更低。
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
if (temp != null && temp.val == val) {
return temp;
} else if (temp != null && temp.val > val) {
queue.offer(temp.left);
} else if (temp != null && temp.val < val) {
queue.offer(temp.right);
}
}
return null;
}
06 小結
演算法專題目前已日更超過四個月 ，演算法題文章163 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！