Leetcode-110. 平衡二叉树

发表于 分类于 阅读次数：

题目链接：https://leetcode-cn.com/problems/balanced-binary-tree/

解法1：递归

思路：

判断每一个节点的左子树和右子树高度，若左右高度差大于1直接返回false

按照这个思路我们能写出下面两个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL)
            return true;
        int l=highbool(root->left,0);
        int r=highbool(root->right,0);
        return abs(l-r)<=1&&isBalanced(root->left)&&isBalanced(root->right);
    }
    int highbool(TreeNode *root,int height)
    {
        if(root==NULL)
            return height;
        return max(highbool(root->left,height+1),highbool(root->right,height+1));
    }
};

我们还可加一个私有变量，全局保存res的返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    bool res;
public:
    bool isBalanced(TreeNode* root) {
        res=true;
        highbool(root,0);
        return res;
    }
    int highbool(TreeNode *root,int height)
    {
        if(root==NULL)
            return height;
        int l=highbool(root->left,height+1);
        int r=highbool(root->right,height+1);
        if(abs(l-r)>1)  res=false;
        return max(l,r);
    }
};