Day98 | 灵神 | 二叉树 平衡二叉树

110.平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

思路：

笔者的思路：

就是左右子树高度差不超过1

那就算左子树和右子树高度然后相减，如果超过1就把标记flag变为false即可

灵神的思路：

灵神是失败就返回-1而不使用flag标记

如果最后返回的结果不是-1，那就是true，是的话就是false

完整代码：

笔者的

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

灵神的简洁版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int get_height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_h = get_height(node->left);
        if (left_h == -1) {
            return -1; // 提前退出，不再递归
        }
        int right_h = get_height(node->right);
        if (right_h == -1 || abs(left_h - right_h) > 1) {
            return -1;
        }
        return max(left_h, right_h) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};