题目描述：示例：解析思路1：自顶向下递归（前序遍历）
代码（cpp）代码（python3） 解析思路2：后序遍历 + 剪枝 （从底至顶判断）
代码（cpp）代码（python3）
题目描述：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例：
示例1：给定二叉树 [3,9,20,null,null,15,7]
3 / 9 20 / 15 7- 返回 true 。
示例2：给定二叉树 [1,2,2,3,3,null,null,4,4]
1 / 2 2 / 3 3 / 4 4- 返回 false 。
提示：
0 <= 树的节点个数 <= 10000
解析思路1：自顶向下递归（前序遍历）参考官方解析.容易想到：声明判断当前节点的函数：depth（）计算二叉树中的一个节点的高度；区分 ：root == null 和 root ！= null 时的情况；判断根节点 符合 平衡二叉树 ：bool rootIsBalanced = abs(depth(root->left)-depth(root->right)) <=1;再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡；三者同时满足，即为平衡二叉树。 代码（cpp）
class Solution {public: int depth(TreeNode* root){ //判断当前节点的深度 if (root == NULL) return 0; int leftDeptn = depth(root->left); int rightDepth = depth(root->right); return max(leftDeptn,rightDepth)+1; } bool isBalanced(TreeNode* root) { if (root == NULL) return true; // 根节点为空 bool rootIsBalanced = abs(depth(root->left)-depth(root->right)) <=1; // 判断根节点 bool leftIsBalanced = isBalanced(root->left); // 递归判断左、右子树 bool rightIsBalanced = isBalanced(root->right); return rootIsBalanced && leftIsBalanced && rightIsBalanced; }};
代码优化：
class Solution {public: int height(TreeNode* root) { if (root == NULL) {return 0;} else { return max(height(root->left), height(root->right)) + 1; } } bool isBalanced(TreeNode* root) { if (root == NULL) {return true;} else { return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right); } }};
代码（python3）
复杂度分析：
时间复杂度：O(n^2) ：其中 n 是二叉树中的节点个数，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)；二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)。空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。 解析思路2：后序遍历 + 剪枝 （从底至顶判断）
参考k神-jdy-解析.
不太好想的：
对二叉树做后续遍历，从下往上返回子树的深度，如果存在子树不是平衡二叉树，就 ‘剪枝’ ，直接向上返回。
算法流程示意图：
代码（cpp）class Solution {public: // int depth(TreeNode* root){ //判断当前节点的深度 // if (root == NULL) return 0; // int leftDeptn = depth(root->left); // int rightDepth = depth(root->right); // return max(leftDeptn,rightDepth)+1; // } 用leftDepth，rightDepth记录root左右子节点的深度，避免遍历root时对左右节点的深度进行重复计算。 //考虑到需要同时记录各个节点的深度和其是否符合平衡性要求，这里的返回值设为int,用一个特殊值-1来表示出现不平衡的节点的情况 int postorder(TreeNode* root){ // 后续遍历 二叉树的每个节点（从底至顶）：顺序为 左、右、中 if (root == NULL){return 0;} //root等于0时，该节点符合要求，返回其深度0 int leftDeptn = postorder(root->left); // 从底向上遍历左子节点，leftDeptn最开始的底部深度 为0，顺序为 左、右、中 if (leftDeptn == -1) {return -1;} // 若出现节点的深度为-1，则进行剪枝，开始向上返回，之后的迭代不再进行 int rightDepth = postorder(root->right); // 同理： 从底向上 遍历右子树节点 if (rightDepth == -1){return -1;} return abs(rightDepth-leftDeptn) <2 ? max(leftDeptn,rightDepth)+1:-1;//最开始计算的是左子树最左侧的一个叶节点，其左右子节点不存在，left=0，right=0，满足条件，返回该叶节点的深度max(0,0)+1=1,否则返回 -1 ;返回-1 ，此时代表的不是深度，是一种判断，判断已经是不满足平衡二叉树了，所以返回-1 代表这样结果，之后返回上一层就不要继续递归了，也直接返回-1 } bool isBalanced(TreeNode* root) { return postorder(root)==-1?false:true; // 返回-1 ，此时代表的不是深度，是一种判断，判断已经是不满足平衡二叉树了 };};
代码（python3）
复杂度分析：
时间复杂度 O(N)： N 为树的节点数；最差情况下，需要递归遍历树的所有节点。空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。