[C语言][剑指offer篇]--II. 平衡二叉树（后序遍历 + 剪枝）

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。

如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

理清思路

 后序遍历二叉树，由底向上返回某一子树的深度，并判断是否某一子树是否是平衡树，只要任意子树不是平衡树，则整棵数都不是平衡树：

• 当节点的左右子树的深度差 < 2 ，则返回子树的深度，即：max(left_hight,right_hight)+1 。
  

  
  

• 当节点的左右子树的深度差 > 2，则返回-1，说明不是平衡树。
  

  
  

• 递归终止条件：root == NULL ，说明越过叶子节点，返回0 ；左右子树返回-1，说明不是二叉树，直接返回-1，没有必要再判断其他子树，这就是所谓的剪枝。
  

  
  

代码实现

int max(int a,int b)
 {
     return a > b ? a:b ;
 }

int recur(struct TreeNode* root)
{
    int left_hight = 0;
    int right_hight = 0;

    if(root == NULL)
    {
        return 0;
    }

    left_hight = recur(root->left);
    if(left_hight == -1)
    {
        return -1;
    }

    right_hight = recur(root->right);
    if(right_hight == -1)
    {
        return -1;
    }

    return abs(left_hight - right_hight) < 2 ? (max(left_hight,right_hight)+1) : -1;
}

bool isBalanced(struct TreeNode* root){

    if(recur(root) != -1)
    {
        return true;
    }
    else
    {
        return false;
    }

}