剑指offer 60. 平衡二叉树

简介: 剑指offer 60. 平衡二叉树

题目描述

输入一棵二叉树的根结点,判断该树是不是平衡二叉树

如果某二叉树中任意结点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。

注意:

  • 规定空树也是一棵平衡二叉树。

数据范围

树中节点数量 [0,500]。

样例

输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,
  5
 / \
7  11
  /  \
 12   9
输出:true

方法一:dfs O(n)

这道题只要求我们去判断该树是否为平衡二叉树,不用我们写出完整的代码,如果想对平衡二叉树深入了解的话可以去看看我之前的图解,平衡二叉树也是数据结构必须掌握的知识,传送门放在这里了~


平衡二叉树详细讲解


我们回到这题,如果结果返回 true 则需要满足:


如果 root 是空,则直接返回 true 。

当前 root 需要满足左子树的最大深度与右子树的最大深度只差的绝对值小于等于 1 。

右子树和左子树也需要满足平衡树的要求。

这道题其实是上一道题即求二叉树的深度的扩展,深度的求法和那道题一模一样,先去递归到二叉树的叶子结点再回溯,返回的值是 max(左子树深度,右子树深度) + 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 dfs(TreeNode* root) {
        if (!root)   return 0;
        int left = dfs(root->left), right = dfs(root->right);
        return max(left, right) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if (!root)   return true;
        return isBalanced(root->left) && isBalanced(root->right) && abs(dfs(root->left) - dfs(root->right)) <= 1;
    }
};

欢迎大家在评论区交流~

目录
相关文章
|
6月前
|
消息中间件 Kubernetes NoSQL
剑指offer常见题 - 二叉树问题(三)
剑指offer常见题 - 二叉树问题(三)
|
6月前
|
消息中间件 Kubernetes NoSQL
剑指offer常见题 - 二叉树问题(一)
剑指offer常见题 - 二叉树问题(一)
【剑指offer】-平衡二叉树-37/67
【剑指offer】-平衡二叉树-37/67
|
1月前
【LeetCode 33】110.平衡二叉树
【LeetCode 33】110.平衡二叉树
11 1
|
6月前
|
消息中间件 Kubernetes NoSQL
剑指offer常见题 - 二叉树问题(二)
剑指offer常见题 - 二叉树问题(二)
|
3月前
|
算法 Java 关系型数据库
leetcode110-平衡二叉树
文章通过LeetCode第110题"平衡二叉树"的解题过程,深入讲解了平衡二叉树的定义、树的高度概念,并提供了使用后序遍历算法判断二叉树是否平衡的Java代码实现,强调了理解理论知识和实践编码的重要性。
Leetcode1038. 从二叉搜索树到更大和树(每日一题)
Leetcode1038. 从二叉搜索树到更大和树(每日一题)
LeetCode | 110. 平衡二叉树
LeetCode | 110. 平衡二叉树
|
6月前
|
Java C++ Python
leetcode-110:平衡二叉树
leetcode-110:平衡二叉树
46 0
剑指offer 58. 二叉搜索树的第k个结点
剑指offer 58. 二叉搜索树的第k个结点
53 0