程序员面试经典--二叉树平衡检查

 

题目描述

实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。

给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。

 

/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/class Balance {public:    bool flag;     bool isBalance(TreeNode* root) {        // write code here        flag = true;         GetDepth(root);         return flag;     }     int GetDepth(TreeNode* root){        if(flag == false){            return 0;         }        if(root == NULL){            return 0;         }else if(root->left == NULL && root->right == NULL){            return 1;         }        int lf = GetDepth(root->left);         int rg = GetDepth(root->right);         if(abs(lf - rg) > 1){            flag = false;         }        return max(lf + 1, rg + 1);     }};