110 平衡二叉树

题目描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

方法1：
主要思路：
（1）直观的想，平衡树是通过比较左右子树的高度差，来确定是否是平衡树，则可以在当前结点下，找出左子树，和有子树的高度，比较这两个子树的高度差，若满足要求，则将当前结点作为新的高度增加1，接着向上遍历，若不满足要求，则可以设置个标志，提前终止后面的判断；
（2）根据上述的思路，可以使用后序遍历，在获得左右子树的高度后，进行高度的比较，判读是否满足要求，返回值为以当前结点为根节点的高度，既将左右子树中的较大值加1作为高度返回；

/**
 * 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 {
public:

    int helper(TreeNode* root,bool& is_balanced){
    	//提前终止递归条件
        if(!is_balanced)
            return 0;
        //终止添条件
        if(root==NULL)
            return 0;
        //获得左右子树的高度
        int left_depth=helper(root->left,is_balanced);
        int right_depth=helper(root->right,is_balanced);
        //判断左右子树是否满足要求
        if(abs(left_depth-right_depth)>1)
            is_balanced=false;
        //返回当前结点的高度
        return max(left_depth,right_depth)+1;
    }

    bool isBalanced(TreeNode* root) {
        if(root==NULL)
            return true;
        //标志位
        bool is_balanced=true;
        //后序遍历处理
        helper(root,is_balanced);
        return is_balanced;
    }
};