XTAO's Tech Blog
0%

[Leetcode]110. Balanced Binary Tree(C++)

发表于 更新于 分类于 评论数：
1.5k 1 分钟

题目描述

题目链接：110. Balanced Binary Tree

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 left and right subtrees of every node differ in height by no more than 1.

例子

例子 1

Input: root = [3,9,20,null,null,15,7]
Output: true

例子 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

例子 3

Input: root = []
Output: true

Follow Up

Note

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -10^4 <= Node.val <= 10^4

解题思路

首先我们需要一个 height 函数来求出二叉树的高度，逻辑比较简单：

  • 假如树是空，返回 0
  • 加入根节点是叶节点，返回 1
  • 其余情况返回 max(root->left, root->right) + 1

可以求二叉树高度后，我们只需要判断左右两侧子树的高度是否相差 1 以内即可，同时还要递归地判断左右两棵子树本身是否也平衡，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return isBalanced(root->left) && isBalanced(root->right) &&
               std::abs(height(root->left) - height(root->right)) <= 1;
    }

private:
    int height(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        return std::max(height(root->left), height(root->right)) + 1;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h)

GitHub 代码同步地址： 110.BalancedBinaryTree.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章