669. 修剪二叉搜尋樹 : 常規樹的遍歷與二叉樹性質
題目描述
這是 LeetCode 上的 669. 修剪二叉搜尋樹 ,難度為 中等 。
Tag : 「BST」、「二叉樹」、「遞迴」、「迭代」
給你二叉搜尋樹的根節點 root
,同時給定最小邊界 low
和最大邊界 high
。通過修剪二叉搜尋樹,使得所有節點的值在 $[low, high]$ 中。修剪樹 不應該 改變保留在樹中的元素的相對結構 (即,如果沒有被移除,原有的父代子代關係都應當保留)。 可以證明,存在 唯一的答案 。
所以結果應當返回修剪好的二叉搜尋樹的新的根節點。注意,根節點可能會根據給定的邊界發生改變。
示例 1:
![](http://mdimg.wxwenku.com/getimg/356ed03bdc643f9448b3f6485edc229b848611cf05e47bc2820ecb6b5c1bb07f5c86deee1752ddfe519cc8118019c034.jpg)
輸入:root = [1,0,2], low = 1, high = 2 輸出:[1,null,2]
示例 2:
![](http://mdimg.wxwenku.com/getimg/356ed03bdc643f9448b3f6485edc229b8fe8117c4eb19a78441abac80df553f8e657389be3f5ca9095486fa21e23ae08.jpg)
輸入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3 輸出:[3,2,null,1]
提示:
- 樹中節點數在範圍 $[1, 10^4]$ 內
- $0 <= Node.val <= 10^4$
- 樹中每個節點的值都是 唯一 的
- 題目資料保證輸入是一棵有效的二叉搜尋樹
- $0 <= low <= high <= 10^4$
遞迴
由於被修剪的是二叉搜尋樹,因此修剪過程必然能夠順利進行。
容易想到使用原函式作為遞迴函式:
- 若
root.val
小於邊界值low
,則root
的左子樹必然均小於邊界值,我們遞迴處理root.right
即可; - 若
root.val
大於邊界值high
,則root
的右子樹必然均大於邊界值,我們遞迴處理root.left
即可; - 若
root.val
符合要求,則root
可被保留,遞迴處理其左右節點並重新賦值即可。
Java 程式碼:
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) return null; if (root.val < low) return trimBST(root.right, low, high); else if (root.val > high) return trimBST(root.left, low, high); root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } }
TypeScript 程式碼:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null { if (root == null) return null if (root.val < low) return trimBST(root.right, low, high) else if (root.val > high) return trimBST(root.left, low, high) root.left = trimBST(root.left, low, high) root.right = trimBST(root.right, low, high) return root };
- 時間複雜度:$O(n)$
- 空間複雜度:忽略遞迴帶來的額外空間開銷,複雜度為 $O(1)$
迭代
自然能夠使用「迭代」進行求解:起始先從給定的 root
進行出發,找到第一個滿足值符合 $[low, high]$ 範圍的節點,該節點為最後要返回的根節點 ans
。
隨後考慮如何修剪 ans
的左右節點:當根節點符合 $[low, high]$ 要求時,修剪左右節點過程中僅需考慮一邊的邊界值即可。即對於 ans.left
只需考慮將值小於 low
的節點去掉(因為二叉搜尋樹的特性, ans
滿足不大於 high
要求,則其左節點必然滿足);同理 ans.right
只需要考慮將大於 high
的節點去掉即可。
Java 程式碼:
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left; TreeNode ans = root; while (root != null) { while (root.left != null && root.left.val < low) root.left = root.left.right; root = root.left; } root = ans; while (root != null) { while (root.right != null && root.right.val > high) root.right = root.right.left; root = root.right; } return ans; } }
TypeScript 程式碼:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null { while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left const ans = root while (root != null) { while (root.left != null && root.left.val < low) root.left = root.left.right root = root.left } root = ans while (root != null) { while (root.right != null && root.right.val > high) root.right = root.right.left root = root.right } return ans };
- 時間複雜度:$O(n)$
- 空間複雜度:$O(1)$
最後
這是我們「刷穿 LeetCode」系列文章的第 No.669
篇,系列開始於 2021/01/01,截止於起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們將先把所有不帶鎖的題目刷完。
在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。
為了方便各位同學能夠電腦上進行除錯和提交程式碼,我建立了相關的倉庫: http://github.com/SharingSou... 。
在倉庫地址裡,你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。
更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:
本文由mdnice多平臺釋出
- 天翼雲全場景業務無縫替換至國產原生作業系統CTyunOS!
- 以羊了個羊為例,淺談小程式抓包與響應報文修改
- 這幾種常見的 JVM 調優場景,你知道嗎?
- 如此狂妄,自稱高效能佇列的Disruptor有啥來頭?
- 為什麼要學習GoF設計模式?
- 827. 最大人工島 : 簡單「並查集 列舉」運用題
- 手把手教你如何使用 Timestream 實現物聯網時序資料儲存和分析
- 850. 矩形面積 II : 掃描線模板題
- Java 併發程式設計解析 | 基於JDK原始碼解析Java領域中的併發鎖,我們可以從中學習到什麼內容?
- 【手把手】光說不練假把式,這篇全鏈路壓測實踐探索
- 大廠鍾愛的全鏈路壓測有什麼意義?四種壓測方案詳細對比分析
- 寫個續集,填坑來了!關於“Thread.sleep(0)這一行‘看似無用’的程式碼”裡面留下的坑。
- 857. 僱傭 K 名工人的最低成本 : 列舉 優先佇列(堆)運用題
- Vue3 實現一個自定義toast(小彈窗)
- 669. 修剪二叉搜尋樹 : 常規樹的遍歷與二叉樹性質
- 讀完 RocketMQ 原始碼,我學會了如何優雅的建立執行緒
- 效能調優——小小的log大大的坑
- 1582. 二進位制矩陣中的特殊位置 : 簡單模擬題
- elementui原始碼學習之仿寫一個el-switch
- 646. 最長數對鏈 : 常規貪心 DP 運用題