lc.110 平衡二叉树

描述

---

平衡二叉树的性质：每个节点的左右两个子树的高度差的绝对值不超过 1；

题解

---

以下两种方法均基于以下性质推出：当前树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。

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

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

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return recur(root) != -1;
    }
private:
    int recur(TreeNode* root) {
        if(!root){return 0;}//空根处理
		
		//简化记法
        int left=recur(root->left);
        int right=recur(root->right);

        if(left==-1||right==-1){
            return -1;
        }

        return abs(left - right) <=1 ? max(left, right) + 1 : -1;
    }
};

过程图示

方法二–笨方法

利用 求二叉树的最大深度 的maxDepth函数：

class Solution {
public:

    bool isBalanced(TreeNode* root) {

        if(root){//前序遍历的模板: 遍历每个结点,对它们都进行判断

            if(abs(maxDepth(root->left)-maxDepth(root->right))>1){
                return false;//如果根结点的左右子树不满足|left-right|<=1,则返回false
            }
            
			//这个if语句其实就相当于前序遍历的那两句,只不过把它们放到括号里了
			if(!isBalanced(root->left)||!isBalanced(root->right)){
                return false;//检查左右子树的左右子树是否满足
            }

            return true;//|left-right|<=1

        }
          else{ return true; }//如果当前根节点为空,一定满足|left-right|=0<=1

    }
  

    int maxDepth(TreeNode* root) {//求二叉树最大深度的函数
        if (root == nullptr) return 0;//空结点,返回0
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

};

1. 检查根节点
2. 检查左右子树
3. 如果以上两条都不为false，则返回true
4. 如果是空结点，也返回true

这个方法虽然好理解一些，但时间复杂度很高（不过还是AC了）