110. Balanced Binary Tree

阳光穿透心脏的1/2处 2022-06-08 14:59 180阅读 0赞

题目描述：

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.

思路详解：

设置一个高度h与平衡因子balance，如果平衡，则为1，如果不平衡，则为0.如果节点为空，则为h=0,balance = 1;如果节点无孩子 ,h=1,balance = 1;

再向上比较balance即可。

答案详解：

/\*\*

\* 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:  
    void judge(TreeNode\* root, int &balance,int &h)  
    \{  
         int br,bl,hr,hl;  
        if(root==NULL)  
        \{  
            balance=1;  
            h=0;  
        \}  
        else if(root->left==NULL&&root->right==NULL)  
        \{  
            balance=1;  
            h=1;  
        \}  
        else  
        \{  
            judge(root->left,bl,hl);  
            judge(root->right,br,hr);  
            h=(hr > hl ? hr : hl)+1;  
            if(abs(hr-hl)<2)  
                balance=bl&br;  
            else  
                balance=0;  
        \}  
\}  
  
    bool isBalanced(TreeNode\* root) \{  
        int balance,h;  
        judge(root,balance,h);  
        return balance;  
    \}  
\};

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 110. Balanced Binary Tree

Topic Tree Depth-first Search Recursion Description [https://leetcode.co

小灰灰/ 2022年12月28日 09:05/ 0 赞/ 132 阅读

相关 LeetCode110—Balanced Binary Tree

LeetCode110—Balanced Binary Tree 原题 > Given a binary tree, determine if it is heig

偏执的太偏执、/ 2022年07月28日 05:12/ 0 赞/ 156 阅读

相关 110. Balanced Binary Tree （平衡二叉树判断）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

迈不过友情╰/ 2022年07月15日 01:18/ 0 赞/ 144 阅读

相关 110. Balanced Binary Tree （平衡二叉树判断）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

港控/mmm°/ 2022年07月15日 01:18/ 0 赞/ 160 阅读

相关 [leetcode]: 110. Balanced Binary Tree

1.题目 Given a binary tree, determine if it is height-balanced. For this problem, a he

爱被打了一巴掌/ 2022年06月15日 05:20/ 0 赞/ 181 阅读

相关 110. Balanced Binary Tree

题目描述： Given a binary tree, determine if it is height-balanced. For this problem, a hei

阳光穿透心脏的1/2处/ 2022年06月08日 14:59/ 0 赞/ 181 阅读

相关 LeetCode 110.Balanced Binary Tree (平衡二叉树)

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为： > 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例

小鱼儿/ 2022年05月09日 04:56/ 0 赞/ 148 阅读

相关 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

系统管理员/ 2022年03月26日 08:59/ 0 赞/ 186 阅读

相关【Leetcode】110. Balanced Binary Tree（平衡二叉树）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

小灰灰/ 2022年02月17日 14:35/ 0 赞/ 205 阅读

相关 LeetCode 110. Balanced Binary Tree平衡二叉树 (C++)

题目： Given a binary tree, determine if it is height-balanced. For this problem, a hei

以你之姓@/ 2021年12月22日 03:11/ 0 赞/ 197 阅读