LeetCode演算法題-Trim a Binary Search Tree(Java實現)
這是悅樂書的第284 次更新,第301 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第152題(順位題號是669)。給定二叉搜尋樹以及L和R的最低和最高邊界,修剪樹以使其所有元素位於[L,R](R> = L)。可能需要更改樹的根,因此結果應返回修剪後的二叉搜尋樹的新根。例如:
輸入:L = 1R = 2
1 / \ 02
輸出:
1 \ 2
輸入:L = 1R = 3
3 / \ 04 \ 2 / 1
輸出:
3 / 2 / 1
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
使用遞迴的方式。因為是二叉搜尋樹,並且返回的新二叉樹的根節點值是未定的,需要先確定根節點在哪,確定完根節點後,再去確定它的左子樹和右子樹。如果當前節點值比右邊界要大,那麼新節點只可能在左子樹那邊;如果當前節點值比左邊界還要小,那麼新節點只能在右子樹那邊。剩下就是正常情況,新左節點還是在左邊,新右節點還是在右邊。
/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { if (root == null) { return null; } if (root.val > R) { return trimBST(root.left, L, R); } if (root.val < L) { return trimBST(root.right, L, R); } root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); return root; } }
03 第二種解法
使用迭代的方式。首先,還是需要確定根節點在哪裡,使用一個迴圈來判斷,如果當前節點值大於右邊界,就往左子樹裡面找,如果小於左邊界,就往右子樹裡面找。接著,從確定好的根節點開始,處理它的左子樹,還是還是用迴圈,如果當前節點不為空,並且它的左節點本身也不為空,它的左節點值小於左邊界,那麼就跟換它的左節點,將當前節點的左節點重新指向到當前節點左節點的右子節點。同理,對於右子樹的處理也是一樣的邏輯,只是將判斷換成了大於右邊界值。最後返回新的二叉樹。
/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { if (root == null) { return null; } // 先確定根節點的位置 while (root.val > R || root.val < L) { if (root == null) { return null; } if (root.val > R) { root = root.left; } if (root.val < L) { root = root.right; } } // 處理左子樹 TreeNode temp = root; while (temp != null) { // 如果當前節點的左節點不為空且節點值小於左邊界 while (temp.left != null && temp.left.val < L) { // 就將當前節點的左節點指向當前節點左節點的右子節點 temp.left = temp.left.right; } temp = temp.left; } // 處理右子樹 temp = root; while (temp != null) { // 如果當前節點的右節點不為空且節點值大於右邊界 while (temp.right != null && temp.right.val > R) { // 就將當前節點的右節點指向當前節點右節點的左子節點 temp.right = temp.right.left; } temp = temp.right; } return root; } }
04 小結
演算法專題目前已日更超過四個月,演算法題文章152 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!