题目描述

给定一个二叉树，判断它是否是平衡二叉树。

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

题目分析

其实平衡二叉树的定义就给出了递归的思路：每个节点的左右两个子树的高度差的绝对值不超过1。那么我们递归从下往上计算每个节点左右子树的高度差，并进行判断就好了。显而易见，我们这里是后序遍历，因为要先计算左右子树，然后把左右子树的情况传给当前根节点，依此向上传递。

1. 首先确定函数返回值及参数：我们需要计算左右子树高度，那么就需要传回int类型值。但是当发现左右子树不是平衡二叉树时，我们其实可以不用再向上计算了，因为这棵树必定就不是平衡二叉树了。那么我们可以设定返回值为-1时，能判定以当前节点为根节点的子树不是平衡二叉树。
2. 递归终止条件：当节点没有左右子树了，即遍历到叶子节点时，我们就直接返回叶子节点的高度，也就是0；
3. 每层递归的逻辑：按照后序遍历的方法，也就是左-右-中。但这里需要注意，我们每遍历完一个左子树或右子树，都要判断它是不是平衡二叉树，也即返回值是否为-1，如果是-1，那就直接向上层递归返回-1即可。

整体代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int compare(TreeNode* root){// 递归计算并判断每个节点左子树右子树的高度差// 递归终止条件if(root==NULL) return 0;// 设置返回值-1说明左右子树不平衡// 后序遍历int leftHeight = compare(root->left);if(leftHeight == -1) return -1;int rightHeight = compare(root->right);if(rightHeight == -1) return -1;if(abs(leftHeight-rightHeight) > 1) return -1;return 1 + max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {int result = compare(root);if(result == -1) return false;else return true;}
};