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

以你之姓@ 2021-12-22 03:11 199阅读 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.

Example 1:

Given the following tree `[3,9,20,null,null,15,7]`:

3
       / \
      9  20
        /  \
       15   7

Return true.  
  
Example 2:

Given the following tree `[1,2,2,3,3,null,null,4,4]`:

1
          / \
         2   2
        / \
       3   3
      / \
     4   4

Return false.

## 分析： ##

给定一个二叉树，判断它是否是高度平衡的二叉树。

一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

递归求解每个节点的左右两个子树的高度差的绝对值是否超过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:
        bool isBalanced(TreeNode* root) {
            if(root == nullptr) return true;
            return abs(height(root->left, 0)-height(root->right, 0)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
        int height(TreeNode* root, int h) {
            if(root == nullptr) return h;
            return max(height(root->left, h+1), height(root->right, h+1));
        }
    };

转载于:https://www.cnblogs.com/silentteller/p/10854504.html

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode110-Balanced Binary Tree

LeetCode 110 : Balanced Binary Tree Given a binary tree, determine if it is height-bala

落日映苍穹つ/ 2022年08月04日 12:48/ 0 赞/ 6 阅读

相关 LeetCode110—Balanced Binary Tree

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

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

相关 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 赞/ 146 阅读

相关 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 赞/ 162 阅读

相关 [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 赞/ 182 阅读

相关 [Leetcode][python]Balanced Binary Tree/平衡二叉树

题目大意判断一颗二叉树是否是“高度”平衡的。平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。这实际上是[AVL树（维基百科）][AVL]

喜欢ヅ旅行/ 2022年06月11日 08:16/ 0 赞/ 171 阅读

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

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

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

相关【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 赞/ 208 阅读

相关 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 赞/ 200 阅读

相关 LeetCode : 110. Balanced Binary 平衡二叉树

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

一时失言乱红尘/ 2021年06月24日 16:10/ 0 赞/ 317 阅读