【剑指offer】平衡二叉树

考察知识点：二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

题解一

分析

当一棵二叉树的左右子树高度绝对值之差小于等于 1，则为平衡二叉树，否则不是
根据这个思路可以针对每个结点，求其子树高度是否满足条件

代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot)
            return true;
        // 如果最大左右子树高度绝对值之差大于1，则说明不是平衡二叉树
        if(abs(getDepth(pRoot->left)-getDepth(pRoot->right))>1)
            return false;
         // 递归左子树
        if(!IsBalanced_Solution(pRoot->left))
            return false;
         // 递归右子树
        if(!IsBalanced_Solution(pRoot->right))
            return false;
        return  true;
    }
    // 求最大子树高度函数
    int getDepth(TreeNode* pRoot){
        if(pRoot){
            int left = getDepth(pRoot->left);
            int right = getDepth(pRoot->right);
            return max(left,right) + 1;
        }
        return 0;
    }
};

题解二

分析

分析上一周解法，可以发现为了求树高，每个结点都会向下遍历它的子树一次
我们可以考虑优化，当发现某个结点不是平衡二叉树了，停止整个遍历

代码

class Solution {
public:
	// 当返回 -1 即代表不是平衡二叉树，返回 false
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return  getDepth(pRoot) != -1 ;
    }
    // 当返回 -1 即代表不是平衡二叉树
    // 当接受到 -1 即递归该结束了
    int getDepth(TreeNode* pRoot){
        if(pRoot){
            int left = getDepth(pRoot->left);
            if(left==-1)
                return -1;
            int right = getDepth(pRoot->right);
            if(right == -1)
                return -1;
            if(abs(left-right)>1)
                return -1;
            return max(left,right)+1;
        }
        return 0;
    }
};