题目：

链接：剑指 Offer 55 - II. 平衡二叉树；LeetCode 110. 平衡二叉树
难度：简单

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

后序遍历：

后序遍历过程中，对每个节点，计算左右子树深度，比较左右深度差判断是否平衡，若平衡则将较大子树的深度向上传递。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:bool flag = true;  // 是否平衡
public:bool isBalanced(TreeNode* root) {depth(root);return flag;}int depth(TreeNode* root) {  // 搜索子树的深度if(root == nullptr) return 0;int leftDepth = depth(root->left);  // 左子树深度int rightDepth = depth(root->right);  // 右子树深度if(abs(leftDepth - rightDepth) > 1) {  // 左右子树深度差大于1，则整棵树不平衡flag = false;return -1;}return max(leftDepth + 1, rightDepth + 1);  // 向上传递该子树深度}
};

时间复杂度O(N)。每个节点处判断一次平衡。
空间复杂度O(N)。递归栈所需的空间在二叉树退化为链表时取得最大值。