平衡二叉樹專題 · ttttt

# 平衡二叉樹專題 # 衡二叉樹專題力扣關于平衡二叉樹的題目還是有一些的，并且都非常經典，推薦大家練習。今天給大家精選了 4 道題，如果你徹底搞明白了這幾道題，碰到其他的平衡二叉樹的題目應該不至于沒有思路。當你領會了我的思路之后，建議再找幾個題目練手，鞏固一下學習成果。 ## 110. 平衡二叉樹（簡單）最簡單的莫過于判斷一個樹是否為平衡二叉樹了，我們來看下。 ### 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹，判斷它是否是高度平衡的二叉樹。本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過1。示例 1: 給定二叉樹 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。示例 2: 給定二叉樹 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false ``` ``` ### 思路由于平衡二叉樹定義為就是**一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。**用偽代碼描述就是： ``` <pre class="calibre18">``` if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉樹 and root.right 也是平衡二叉樹: print('是平衡二叉樹') else: print('不是平衡二叉樹') ``` ``` 而 root.left 和 root.right **如何判斷是否是二叉平衡樹就和 root 是一樣的了**，可以看出這個問題有明顯的遞歸性。因此我們首先需要知道如何計算一個子樹的高度。這個可以通過遞歸的方式輕松地計算出來。計算子樹高度的 Python 代碼如下： ``` <pre class="calibre18">``` def dfs(node, depth): if not node: return 0 l = dfs(node.left, depth + 1) r = dfs(node.right, depth + 1) return max(l, r) + 1 ``` ``` ### 代碼代碼支持： Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def isBalanced(self, root: TreeNode) -> bool: def dfs(node, depth): if not node: return 0 l = dfs(node.left, depth + 1) r = dfs(node.right, depth + 1) return max(l, r) + 1 if not root: return True if abs(dfs(root.left, 0) - dfs(root.right, 0)) > 1: return False return self.isBalanced(root.left) and self.isBalanced(root.right) ``` ``` **復雜度分析** - 時間復雜度：對于 isBalanced 來說，由于每個節點最多被訪問一次，這部分的時間復雜度為 O(N)O(N)O(N)，而 dfs 函數每次被調用的次數不超過 logNlog NlogN，因此總的時間復雜度為 O(NlogN)O(NlogN)O(NlogN)，其中 NNN 為樹的節點總數。 - 空間復雜度：由于使用了遞歸，這里的空間復雜度的瓶頸在棧空間，因此空間復雜度為 O(h)O(h)O(h)，其中 hhh 為樹的高度。 ## 108. 將有序數組轉換為二叉搜索樹（簡單） 108 和 109 基本是一樣的，只不過數據結構不一樣，109 變成了鏈表了而已。由于鏈表操作比數組需要考慮更多的因素，因此 109 是中等難度。 ### 題目描述 ``` <pre class="calibre18">``` 將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。示例: 給定有序數組: [-10,-3,0,5,9], 一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5 ``` ``` ### 思路對于這個問題或者 `給定一個二叉搜索樹，將其改為平衡（后面會講）` 基本思路都是一樣的。題目的要求是將有序數組轉化為： 1. 高度平衡的二叉樹 2. 二叉搜索樹由于平衡二叉樹是左右兩個子樹的高度差的絕對值不超過 1。因此一種簡單的方法是**選擇中點作為根節點，根節點左側的作為左子樹，右側的作為右子樹即可。**原因很簡單，這樣分配可以保證左右子樹的節點數目差不超過 1。因此高度差自然也不會超過 1 了。上面的操作同時也滿足了二叉搜索樹，原因就是題目給的數組是有序的。 > 你也可以選擇別的數作為根節點，而不是中點，這也可以看出答案是不唯一的。 ### 代碼代碼支持： Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: if not nums: return None mid = (len(nums) - 1) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid + 1:]) return root ``` ``` **復雜度分析** - 時間復雜度：由于每個節點最多被訪問一次，因此總的時間復雜度為 O(N)O(N)O(N)，其中 NNN 為數組長度。 - 空間復雜度：由于使用了遞歸，這里的空間復雜度的瓶頸在棧空間，因此空間復雜度為 O(h)O(h)O(h)，其中 hhh 為樹的高度。同時由于是平衡二叉樹，因此 hhh 就是 logNlog NlogN。 ## 109. 有序鏈表轉換二叉搜索樹（中等） ### 題目描述 ``` <pre class="calibre18">``` `給定一個單鏈表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。示例: 給定的有序鏈表： [-10, -3, 0, 5, 9], 一個可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5 ``` ``` ### 思路和 108 思路一樣。不同的是數據結構的不同，因此我們需要關注的是鏈表和數組的操作差異。 ![](https://img.kancloud.cn/16/af/16af423d72335793d2e9ccb9608e7d8d_1586x740.jpg) （數組的情況）我們再來看下鏈表： ![](https://img.kancloud.cn/eb/0e/eb0ebfdd4d3da35bba81cd36fac7893b_1586x766.jpg)（鏈表的情況）找到中點，只需要使用經典的快慢指針即可。同時為了防止環的出現，我們需要斬斷指向 mid 的 next 指針，因此需要記錄一下中點前的一個節點，這只需要用一個變量 pre 記錄即可。 ### 代碼代碼支持： Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: if not head: return head pre, slow, fast = None, head, head while fast and fast.next: fast = fast.next.next pre = slow slow = slow.next if pre: pre.next = None node = TreeNode(slow.val) if slow == fast: return node node.left = self.sortedListToBST(head) node.right = self.sortedListToBST(slow.next) return node ``` ``` **復雜度分析** - 時間復雜度：由于每個節點最多被訪問一次，因此總的時間復雜度為 O(N)O(N)O(N)，其中 NNN 為鏈表長度。 - 空間復雜度：由于使用了遞歸，這里的空間復雜度的瓶頸在棧空間，因此空間復雜度為 O(h)O(h)O(h)，其中 hhh 為樹的高度。同時由于是平衡二叉樹，因此 hhh 就是 logNlog NlogN。 ## 1382. 將二叉搜索樹變平衡（中等） ### 題目描述 ``` <pre class="calibre18">``` 給你一棵二叉搜索樹，請你返回一棵平衡后的二叉搜索樹，新生成的樹應該與原來的樹有著相同的節點值。如果一棵二叉搜索樹中，每個節點的兩棵子樹高度差不超過 1 ，我們就稱這棵二叉搜索樹是平衡的。如果有多種構造方法，請你返回任意一種。示例： ``` ``` ![](https://img.kancloud.cn/8c/6a/8c6ab401582bd92b0c08467f9faebb26_235x279.jpg) ``` <pre class="calibre18">``` 輸入：root = [1,null,2,null,3,null,4,null,null] 輸出：[2,1,3,null,null,null,4] 解釋：這不是唯一的正確答案，[3,1,4,null,2,null,null] 也是一個可行的構造方案。提示：樹節點的數目在 1 到 10^4 之間。樹節點的值互不相同，且在 1 到 10^5 之間。 ``` ``` ### 思路由于`二叉搜索樹的中序遍歷是一個有序數組`，因此問題很容易就轉化為 `108. 將有序數組轉換為二叉搜索樹（簡單）`。 ### 代碼代碼支持： Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def inorder(self, node): if not node: return [] return self.inorder(node.left) + [node.val] + self.inorder(node.right) def balanceBST(self, root: TreeNode) -> TreeNode: nums = self.inorder(root) def dfs(start, end): if start == end: return TreeNode(nums[start]) if start > end: return None mid = (start + end) // 2 root = TreeNode(nums[mid]) root.left = dfs(start, mid - 1) root.right = dfs(mid + 1, end) return root return dfs(0, len(nums) - 1) ``` ``` **復雜度分析** - 時間復雜度：由于每個節點最多被訪問一次，因此總的時間復雜度為 O(N)O(N)O(N)，其中 NNN 為鏈表長度。 - 空間復雜度：雖然使用了遞歸，但是瓶頸不在棧空間，而是開辟的長度為 NNN 的 nums 數組，因此空間復雜度為 O(N)O(N)O(N)，其中 NNN 為樹的節點總數。 ## 總結本文通過四道關于二叉平衡樹的題幫助大家識別此類型題目背后的思維邏輯，我們來總結一下學到的知識。平衡二叉樹指的是：`一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過1。` 如果需要讓你判斷一個樹是否是平衡二叉樹，只需要死扣定義，然后用遞歸即可輕松解決。如果需要你將一個數組或者鏈表（邏輯上都是線性的數據結構）轉化為平衡二叉樹，只需要隨便選一個節點，并分配一半到左子樹，另一半到右子樹即可。同時，如果要求你轉化為平衡二叉搜索樹，則可以選擇排序數組(或鏈表)的中點，左邊的元素為左子樹，右邊的元素為右子樹即可。 > 小提示 1：如果不需要是二叉搜索樹則不需要排序，否則需要排序。 > > 小提示 2：你也可以不選擇中點，算法需要相應調整，感興趣的同學可以試試。 > > 小提示 3：鏈表的操作需要特別注意環的存在。更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。