作者：whisper

链接：https://www.proprogrammar.com/article/871

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 55 - II. 平衡二叉树

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

限制：

• 0 <= 树的结点个数 <= 10000

难度：简单；标签：树，深度优先搜索；编程语言：C++

 我的解法

/**
 * 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 {
    bool res;
public:
    bool isBalanced(TreeNode* root) {
        int h = 0;
        res = true;
        heightBalance(root, &h);

        return res;
    }

    void heightBalance(TreeNode* node, int* h){
        if(!res)return;

        if(node){
            if(!node->left && !node->right){
                *h = 1;
            }else{
                *h = 0;
                heightBalance(node->left, h);
                int l = *h;

                *h = 0;
                heightBalance(node->right, h);
                int r = *h;

                if(abs(r - l) > 1)res = false;
                *h = max(l, r) + 1;
            }
        }
    }
};

方法：找出左右深度，判断是否平衡，然后加上自己的深度1，供上一层次使用，如果出现不平衡，就可以return了

实现：深度递归，用一个指针h记录深度，分别计算左、右深度和当前深度（max(l, r)+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 recur(TreeNode* root)
   {
    //    叶子结点，0层
       if(root==NULL)
         return 0;
        int leftlevel=recur(root->left);
        if(leftlevel==-1)
        {
            return -1;
        }
        int rightlevel=recur(root->right);
        if(rightlevel==-1)
           return-1;
        if(rightlevel-leftlevel>1||rightlevel-leftlevel<-1)
           return -1;
        else
        {
            return max(rightlevel,leftlevel)+1;
        }
   }
    bool isBalanced(TreeNode* root) {
        if(recur(root)==-1)
         return false;
        else 
         return true;

    }
};

基本一致，不再多说，区别是我的解法把深度保存在参数*h中，这里保存在返回值中

亲爱的读者：有时间可以点赞评论一下