题目描述
题目链接：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 以内即可，同时还要递归地判断左右两棵子树本身是否也平衡，代码如下：
/**
* 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