Jianbo Dai's

jz055II.平衡二叉树

 
  • Oct 14, 2020

题目链接

有了求二叉树的深度的经验之后来做这个问题，我们很容易想到一种思路，就是在遍历树的每个节点的时候，调用函数treeDepth得到它的左右子树的深度。如果每个节点的左右字数的深度相差都不超过1，那么按照定义它就是一颗平衡二叉树，这种思路对应的代码如1所示。这个算法的时间复杂度是O（NlogN）：在最差情况下（为“满二叉树”时），isBalanced遍历树所有节点，判断每个节点的深度需要遍历各子树的所有节点。满二叉树高度为O（logN），将满二叉树按层分为log（N+1）层，通过调用treeDepth来判断二叉树各层的节点对应子树的深度，需遍历节点数量为N x 1，$\frac{N-1}{2}$ x 2，$\frac{N-3}{4}$ x 4，$\frac{N-7}{8}$ x 8,…, 1 x $\frac{N+1}{2}$，因此各层执行的时间复杂度为O（N）。因此总时间复杂度为O（NxlogN）。另外，当树退化成链表时空间复杂度是O（N）。

上一种方法中，我们注意到一个节点会被重复遍历多次，这种思路的时间效率不高。接下来我们介绍一种不需要重复遍历的算法。如果我们用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们已经遍历了它的左右子树。只要在遍历每个节点的时候记录它的深度，我们就可以一边遍历一边判断每个节点是不是平衡的。该算法实现如2所示，其时间复杂度为O（N），空间复杂度也为O（N）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced1(self, root: TreeNode) -> bool:
        if not root:
            return True
        left = self.treeDepth(root.left)
        right = self.treeDepth(root.right)
        diff = left - right
        if diff > 1 or diff < -1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def treeDepth(self, node):
        if not node:
            return 0
        return max(self.treeDepth(node.left), self.treeDepth(node.right)) + 1

    def isBalanced2(self, root: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            if left == -1:
                return -1
            right = dfs(node.right)
            if right == -1:
                return -1
            return max(left, right) + 1 if abs(left-right) <= 1 else -1
        return dfs(root) != -1
Search