自顶至底先序递归；自底至顶后序递归。

题目

给定一个二叉树，判断它是否是高度平衡的二叉树

本题中，一棵高度平衡二叉树定义为：

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

示例 1：

   3
  /  \
 9   20
    /  \
   15  7

输入：root = [3,9,20,null,null,15,7]
输出：true

示例2：

      1
     /  \
    2   2
   /  \
  3   3
 /  \
4   4

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from queue import Queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def create_tree(list_tree):
    if  not list_tree:
        return []
    new_queue= Queue()
    root = TreeNode(list_tree[0])
    new_queue.put(root) # 先入队一个结点
    count = 1
    while not new_queue.empty() and count<len(list_tree):
        dequeue = new_queue.get() # 出队
        if not dequeue.left and  not dequeue.right:
            if count<len(list_tree) and list_tree[count]:
                dequeue.left=TreeNode(list_tree[count])
            count= count+1
            if count<len(list_tree) and list_tree[count]:
                dequeue.right=TreeNode(list_tree[count])
            count= count+1

            if dequeue.left:
                new_queue.put(dequeue.left)
            if dequeue.right:
                new_queue.put(dequeue.right)
    return root

方法一：自顶向下的递归

思路

构造一个获取当前节点最大深度的方法 depth(root) ，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。

算法流程：

isBalanced(root)：判断树root是否平衡

  • 特例处理：若root为空，直接返回true
  • 返回值：所有子树都满足平衡树性质，因此以下三者使用与逻辑&&连接
    1. abs(self.depth(root.left)-self.depth(root.right))<=1：判断当前子树是否平衡树
    2. self.isBalanced(root.left)：先序遍历递归，判断当前子树的左子树是否是平衡树
    3. self.isBalanced(root.right：先序遍历递归，判断当前子树的右子树是否是平衡树

depth(root)：计算树root的最大高度

  • 终止条件：当root为空，即越过叶子结点，返回高度0
  • 返回值：返回左/右子树的最大高度加1

复杂度分析

  • 时间复杂度：$O(Nlog_2N)$：最差情况下，isBalanced(root遍历树的所有结点，占用$O(N)$；判断每个结点的最大高度depth(root需遍历各子树的所有结点，子树的结点数的复杂度为$O(log_2N)$

  • 空间复杂度O(N)：最差情况下（树退化为链表），系统递归所需使用O(N)的栈空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

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


root =  [1,2,2,3,3,None,None,4,4]
root_tree=create_tree(root)
a=Solution()
result =a.isBalanced(root_tree)
result
False

方法二：从底至顶（提前阻断）

此方法为本题的最优解法，但“从底至顶”的思路不易第一时间想到。

思路

思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

算法流程：

recur(root)：

  • 递归返回值：

    1. 当结点root左/右子树的高度差<2：返回以结点root为根结点的子树的最大高度，即结点root的左右子树中最大高度加1：（max(left,right)+1）
    2. 当结点root左/右子树的高度差$ \geq 2$：则返回-1，代表此子树不是平衡树

  • 递归终止条件

    1. 当越过叶子结点，返回高度0
    2. 当左右子树高度left=-1时，代表此树的左（右）子树不是平衡树，因此直接返回-1

isBalanced(root)

  • 返回值：若$recur(root)!=-1$，则说明此树平衡返回true；否则返回false

复杂度分析

时间复杂度 O(N)： N为树的节点数；最差情况下，需要递归遍历树的所有节点。

空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.recur(root) != -1

    def recur(self, root):
        if not root: return 0
        
        left = self.recur(root.left)
        if left == -1: return -1

        right = self.recur(root.right)
        if right == -1: return -1

        
        return max(left, right) + 1 if abs(left - right) < 2 else -1
    
root =  [1,2,2,3,3,None,None,4,4]
root_tree=create_tree(root)
a=Solution()
result =a.isBalanced(root_tree)
result
False

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2020/12/06/LeetCode-B-%E4%BA%8C%E5%8F%89%E6%A0%91-110.%20%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/