当前位置：首页 > article >正文

[E二叉树] lc110. 平衡二叉树(dfs+自底向上)

article 2024/9/20 12:01:31

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：110. 平衡二叉树

题单：

1. 链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
- §2.3 自底向上 DFS

2. 题目解析

思路：

记录每个节点的左右子树的高度，并判断高度差是否大于 1 即可。
二叉树计算高度，可看 [E二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)
注意本题可以剪枝优化。如果有任意两个节点的高度差大于 1 了，那么说明整个树都不平衡，则可以直接 return 即可。
故，将代码集中在高度计算中实现代码逻辑即可。

时间复杂度： $O (n)$
空间复杂度： $O (n)$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int hl = dfs(root->left);
        if (hl == -1) return -1;

        int hr = dfs(root->right);
        if (hr == -1) return -1;

        if (abs(hr - hl) > 1) return -1;

        return max(hl, hr) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return dfs(root) != -1;
    }
};