110.Balanced Binary Tree¶
Tags: Tree
Depth-first Search
Easy
Links: https://leetcode.com/problems/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.
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.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <cmath>
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root) return true;
if (isBalanced(root -> left) && isBalanced(root -> right)) {
int leftHeight = height(root -> left);
int rightHeight = height(root -> right);
if (abs(leftHeight - rightHeight) > 1) return false;
else return true;
}
return false;
}
int height(TreeNode *root) {
if (!root) return 0;
if (!root -> left && !root -> right) return 1;
return max(height(root -> left), height(root -> right)) + 1;
}
};
非常容易写出来的递归写法。但是还可以进行优化,因为我们每次计算高度都要遍历此节点以下的节点,实际上如果此节点的子树不是平衡的, 那么无须再检查了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <cmath>
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (checkDepth(root) == -1) return false;
return true;
}
int checkDepth(TreeNode *root) {
if (!root) return 0;
int leftHeight = checkDepth(root -> left);
if (leftHeight == -1) return -1;
int rightHeight = checkDepth(root -> right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return max(leftHeight, rightHeight) + 1;
}
};
如果我们发现子树不平衡,则不计算具体的深度,而是直接返回-1。那么优化后的方法为:对于每一个节点,我们通过checkDepth函数
递归获得左右子树的深度,如果子树是平衡的,则返回真实的深度,若不平衡,直接返回-1,此方法时间复杂度O(N),空间复杂度O(H)