LeetCode 110 Balanced Binary Tree(平衡二叉树)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50554185 翻译给定一个二叉树,决定它是否是高度平衡的。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50554185

翻译

给定一个二叉树,决定它是否是高度平衡的。(高度是名词不是形容词……

对于这个问题,一个高度平衡二叉树被定义为:

这棵树的每个节点的两个子树的深度差不能超过1。

原文

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as 

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

分析

这道题,我认为非常有意义,考察得也很全面。我认为的主要是有以下几个方面:

1,考察各种边界条件
2,考察递归以及对树的遍历
3,考察求解树的高度

先从小的模块开始写,也就是树的高度。其实我看下面的代码,或者说这几天的代码,都是怎么看怎么不顺眼,不知道是不是因为天气太冷让我思维都和身体一样僵硬了。今天中雪……明天就要达到老家的历史最低温了。

int getHeight(TreeNode* root) {
    int left = 0, right = 0;
    if (!root || (!root->left &&!root->right))
        return 0;
    if (root->left != NULL)
        left = 1 + getHeight(root->left);
    if (root->right != NULL)
        right = 1 + getHeight(root->right);
    return max(left, right);
}

通过不断的从上往下的递归来求出它的高度,因为是求最大的高度,所以用了max函数。

因为上面的函数是求的一个节点下面的最大深度,而不包括该节点,所以在下面的函数中用了三目运算符来求出当前节点的深度。后面继续使用了abs函数来求绝对值。

接着就是继续递归了,如果有一步(一个节点)不满足条件,那么就直接返回假了 (不妥协……

bool isBalanced(TreeNode* root) {
    if (!root || (!root->left && !root->right))  return true;
    int left = root->left == NULL ? 0 : getHeight(root->left) + 1;
    int right = root->right == NULL ? 0 : getHeight(root->right) + 1;
    if (abs(left - right) > 1)
        return false;
    else  if (!isBalanced(root->left) || !isBalanced(root->right))
        return false;
    return true;
}

这道题我觉得还是蛮难的,还是要多反复的琢磨琢磨了。

代码

/**
* 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 getHeight(TreeNode* root) {
        int left = 0, right = 0;
        if (!root || (!root->left &&!root->right))
            return 0;
        if (root->left != NULL)
            left = 1 + getHeight(root->left);
        if (root->right != NULL)
            right = 1 + getHeight(root->right);
        return max(left, right);
    }

    bool isBalanced(TreeNode* root) {
        if (!root || (!root->left && !root->right))         return true;
        int left = root->left == NULL ? 0 : getHeight(root->left) + 1;
        int right = root->right == NULL ? 0 : getHeight(root->right) + 1;
        if (abs(left - right) > 1)
            return false;
        else  if (!isBalanced(root->left) || !isBalanced(root->right))
            return false;
        return true;
    }
};
目录
相关文章
|
1月前
【LeetCode 33】110.平衡二叉树
【LeetCode 33】110.平衡二叉树
11 1
|
6月前
leetcode代码记录(平衡二叉树
leetcode代码记录(平衡二叉树
35 0
|
3月前
|
算法 Java 关系型数据库
leetcode110-平衡二叉树
文章通过LeetCode第110题"平衡二叉树"的解题过程,深入讲解了平衡二叉树的定义、树的高度概念,并提供了使用后序遍历算法判断二叉树是否平衡的Java代码实现,强调了理解理论知识和实践编码的重要性。
|
3月前
|
Python
【Leetcode刷题Python】110. 平衡二叉树
LeetCode第110题"平衡二叉树"的Python解决方案,通过计算二叉树的高度并判断任意两个子树的高度差是否不超过1来确定树是否平衡。
21 2
|
5月前
|
SQL 算法 数据挖掘
力扣110:平衡二叉树
力扣110:平衡二叉树
|
算法
【LeetCode题目详解】(五)144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历、104.二叉树的最大深度、110.平衡二叉树
【LeetCode题目详解】(五)144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历、104.二叉树的最大深度、110.平衡二叉树
53 0
LeetCode | 110. 平衡二叉树
LeetCode | 110. 平衡二叉树
|
6月前
|
Java C++ Python
leetcode-110:平衡二叉树
leetcode-110:平衡二叉树
46 0
LeetCode刷题Day14——二叉树(完全二叉树、平衡二叉树、二叉树路径、左叶子之和)
一、完全二叉树的节点个数 题目链接:222. 完全二叉树的节点个数
|
算法
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
42 0