题目描述
题目链接: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 | /** |
- 时间复杂度: O(n)
- 空间复杂度: O(h)
GitHub 代码同步地址: 110.BalancedBinaryTree.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions