关于leetcode:平衡二叉树专题

力扣对于均衡二叉树的题目还是有一些的，并且都十分经典，举荐大家练习。明天给大家精选了 4 道题，如果你彻底搞明确了这几道题，碰到其余的均衡二叉树的题目应该不至于没有思路。当你体会了我的思路之后，倡议再找几个题目练手，坚固一下学习成绩。

最简略的莫过于判断一个树是否为均衡二叉树了，咱们来看下。

给定一个二叉树，判断它是否是高度均衡的二叉树。本题中，一棵高度均衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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。用伪代码形容就是：

if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是均衡二叉树 and root.right 也是均衡二叉树:
    print('是均衡二叉树')
else:
    print('不是均衡二叉树')

而 root.left 和 root.right 如何判断是否是二叉均衡树就和 root 是一样的了，能够看出这个问题有显著的递归性。

因而咱们首先须要晓得如何计算一个子树的高度。这个能够通过递归的形式轻松地计算出来。计算子树高度的 Python 代码如下：

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:

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)$，而 dfs 函数每次被调用的次数不超过 $log N$，因而总的工夫复杂度为 $O(NlogN)$，其中 $N$ 为树的节点总数。
空间复杂度：因为应用了递归，这里的空间复杂度的瓶颈在栈空间，因而空间复杂度为 $O(h)$，其中 $h$ 为树的高度。

108 和 109 根本是一样的，只不过数据结构不一样，109 变成了链表了而已。因为链表操作比数组须要思考更多的因素，因而 109 是中等难度。

将一个依照升序排列的有序数组，转换为一棵高度均衡二叉搜寻树。本题中，一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它能够示意上面这个高度均衡二叉搜寻树：0
     / \
   -3   9
   /   /
 -10  5

对于这个问题或者 给定一个二叉搜寻树，将其改为均衡（前面会讲） 基本思路都是一样的。

题目的要求是将有序数组转化为：

高度均衡的二叉树
二叉搜寻树

因为均衡二叉树是左右两个子树的高度差的绝对值不超过 1。因而一种简略的办法是 抉择中点作为根节点，根节点左侧的作为左子树，右侧的作为右子树即可。起因很简略，这样调配能够保障左右子树的节点数目差不超过 1。因而高度差天然也不会超过 1 了。

下面的操作同时也满足了二叉搜寻树，起因就是题目给的数组是有序的。

你也能够抉择别的数作为根节点，而不是中点，这也能够看出答案是不惟一的。

代码反对：Python3

Python3 Code:

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)$，其中 $N$ 为数组长度。
空间复杂度：因为应用了递归，这里的空间复杂度的瓶颈在栈空间，因而空间复杂度为 $O(h)$，其中 $h$ 为树的高度。同时因为是均衡二叉树，因而 $h$ 就是 $log N$。

` 给定一个单链表，其中的元素按升序排序，将其转换为高度均衡的二叉搜寻树。本题中，一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:

给定的有序链表：[-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它能够示意上面这个高度均衡二叉搜寻树：0
     / \
   -3   9
   /   /
 -10  5

和 108 思路一样。不同的是数据结构的不同，因而咱们须要关注的是链表和数组的操作差别。

（数组的状况）

咱们再来看下链表：

（链表的状况）

找到中点，只须要应用经典的快慢指针即可。同时为了避免环的呈现，咱们须要斩断指向 mid 的 next 指针，因而须要记录一下中点前的一个节点，这只须要用一个变量 pre 记录即可。

代码反对：Python3

Python3 Code:

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)$，其中 $N$ 为链表长度。
空间复杂度：因为应用了递归，这里的空间复杂度的瓶颈在栈空间，因而空间复杂度为 $O(h)$，其中 $h$ 为树的高度。同时因为是均衡二叉树，因而 $h$ 就是 $log N$。

给你一棵二叉搜寻树，请你返回一棵 均衡后 的二叉搜寻树，新生成的树应该与原来的树有着雷同的节点值。如果一棵二叉搜寻树中，每个节点的两棵子树高度差不超过 1，咱们就称这棵二叉搜寻树是 均衡的。如果有多种构造方法，请你返回任意一种。示例：


输出：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:

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)$，其中 $N$ 为链表长度。
空间复杂度：尽管应用了递归，然而瓶颈不在栈空间，而是开拓的长度为 $N$ 的 nums 数组，因而空间复杂度为 $O(N)$，其中 $N$ 为树的节点总数。

本文通过四道对于二叉均衡树的题帮忙大家辨认此类型题目背地的思维逻辑，咱们来总结一下学到的常识。

均衡二叉树指的是：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

如果须要让你判断一个树是否是均衡二叉树，只须要死扣定义，而后用递归即可轻松解决。

如果须要你将一个数组或者链表（逻辑上都是线性的数据结构）转化为均衡二叉树，只须要轻易选一个节点，并调配一半到左子树，另一半到右子树即可。

同时，如果要求你转化为均衡二叉搜寻树，则能够抉择排序数组 (或链表) 的中点，右边的元素为左子树，左边的元素为右子树即可。

小提示 1：如果不须要是二叉搜寻树则不须要排序，否则须要排序。

小提示 2：你也能够不抉择中点，算法须要相应调整，感兴趣的同学能够试试。

小提示 3：链表的操作须要特地留神环的存在。

关于leetcode:平衡二叉树专题

110. 均衡二叉树（简略）

题目形容

思路

代码

108. 将有序数组转换为二叉搜寻树（简略）

题目形容

思路

代码

109. 有序链表转换二叉搜寻树（中等）

题目形容

思路

代码

1382. 将二叉搜寻树变均衡（中等）

题目形容

思路

代码

总结