题目链接

牛客网

题目描述

平衡二叉树左右子树高度差不超过 1。

解题思路

方法一：先序遍历 + 判断深度 （从顶至底）

此方法容易想到，但会产生大量重复计算，时间复杂度较高。

思路是构造一个获取当前子树的深度的函数 depth(root) ，通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

算法流程：

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 。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return true;
        if(abs(deepMax(pRoot->left)-deepMax(pRoot->right))>1)
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
    }
    int deepMax(TreeNode* root){
        if(root==nullptr)
            return 0;
        return 1+max(deepMax(root->left),deepMax(root->right));
    }
};

• 时间复杂度 O(N log N)： 最差情况下（为 “满二叉树” 时）， isBalanced(root) 遍历树所有节点，判断每个节点的深度 depth(root) 需要遍历 各子树的所有节点 。
• 空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。

方法二：后序遍历 + 剪枝 （从底至顶）

此方法为本题的最优解法，但剪枝的方法不易第一时间想到。

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

算法流程：

recur(root) 函数：

• 返回值：

1. 当节点root 左 / 右子树的深度差 ≤1 ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值 +1 （ max(left, right) + 1 ）；
2. 当节点root 左 / 右子树的深度差 >2 ：则返回 -1，代表 此子树不是平衡树 。

• 终止条件：

1. 当 root 为空：说明越过叶节点，因此返回高度 0 ；
2. 当左（右）子树深度为 -1 ：代表此树的 左（右）子树 不是平衡树，因此剪枝，直接返回 -1 ；

isBalanced(root) 函数：

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

  class Solution {
  public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return recur(pRoot)!=-1;
    }
    int recur(TreeNode* root){
        if(root==nullptr)
            return 0;
        // 如果左子树为平衡树返回左子树最大深度，否则返回-1(剪枝)
        int left = recur(root->left);
        if(left==-1)
            return -1;
        // 如果右子树为平衡树返回右子树最大深度，否则返回-1(剪枝)
        int right = recur(root->right);
        if(right==-1)
            return -1;
        // 如果当前子树为平衡树返回最大深度，否则返回-1(剪枝)
        return abs(left-right)<2?max(left,right)+1:-1;
    }
  };
  

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

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