题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 二叉树的深度：从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 思路： 简单方法：在遍历树的每个节点的时候，通过函数计算得到它的左、右子树的深度，如果每个节点的左、右子树的深度都不超过1，那么它就是平衡二叉树。这种方法通过递归方法，思路简洁，但是由于一个节点会被重复遍历多次，时间效率不高。 优化方法：用后序遍历的方式遍历整棵二叉树，在遍历某节点的左、右子节点之后，可以根据它的左、右子节点的深度判断它是不是平衡的，并得到当前节点的深度。当最后遍历到树的根节点的时候，也就判断了整棵二叉树是不是平衡二叉树。 核心代码如下：
struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth){ if(pRoot == nullptr){ //如果该pRoot为空，则其深度为0 *pDepth = 0; return true; } int left, right; if(IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right)){ //后序遍历左、右子树 int diff = left - right; if(diff >= -1 && diff <= 1){ //某一节点的深度差不超过1时 *pDepth = 1 + (left > right ? left : right); //该节点的深度是其左、右子树深度的较大值加1 return true; } } return false; } bool IsBalanced(BinaryTreeNode* pRoot){ int depth = 0; return IsBalanced(pRoot, &depth); //注意，取的是depth的地址 }