【剑指offer】输入一颗二叉树的根节点，判断是不是平衡二叉树，C++实现

原创博文，转载请注明出处！

# 题目

# 举例

# 思路

由平衡二叉树的定义可知，判断二叉树是否是平衡二叉树的关键在于判断任意结点是否是平衡结点。后序遍历二叉树，判断节点的子树是否平衡并计算节点的子树高度，判断结点是否平衡。如果按后序遍历的顺序，遍历到根节点后，根节点也是平衡结点，则二叉树是平衡二叉树。注意：叶子节点是平衡节点，叶子结点高度为1。

# 代码

  1 //后续遍历二叉树，遍历过程中求子树高度，判断是否平衡
  2 class Solution {
  3 public:
  4     bool IsBalanced(TreeNode *root, int & dep){
  5         // 递归出口
  6         if(root == NULL){
  7             return true;
  8         }
  9 
 10         // 左右子树深度
 11         int left = 0;
 12         int right = 0;
 13 
 14         // 判断左右子树是否是平衡二叉树，并判断左右子树高度差的绝对值是否小于1
 15         if(IsBalanced(root->left,left) && IsBalanced(root->right, right))
 16         {
 17             // 结点左右子树高度差
 18             int dif = left - right;
 19             if(dif>=-1 && dif<=1)
 20             {
 21                  dep = (left > right ? left : right) + 1;
 22                  return true;// 本节点是平衡结点
 23             }
 24             else
 25                 return false;// 本节点不是平衡节点
 26         }
 27         else
 28             return false;    // 本节点不是平衡节点
 29     }
 30     bool IsBalanced_Solution(TreeNode* pRoot) {
 31         int dep = 0;
 32         return IsBalanced(pRoot, dep);
 33     }
 34 };