0%

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

题目描述

题目链接: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