110. Balanced Binary Tree
1. Description
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.
2. Example
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
3. Constraints
- The number of nodes in the tree is in the range [0, 5000].
- $-10^4$ <= Node.val <= $10^4$
4. Solutions
My Accepted Solution
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
private:
// return the height of the tree to judge balance, if the tree is not balanced, we return -1
int getHeight(const TreeNode *i_root)
{
if(!i_root) return 0;
int leftChildHeight, rightChildHeight;
// if the left subtree is not balanced, we don't need to calculate the right one
if((leftChildHeight = getHeight(i_root->left)) == -1
|| (rightChildHeight = getHeight(i_root->right)) == -1
|| abs(leftChildHeight - rightChildHeight) > 1) return -1;
return max(leftChildHeight, rightChildHeight) + 1;
}
public:
// bool isBalanced(TreeNode* root)
bool isBalanced(const TreeNode *i_root)
{
return (getHeight(i_root) != -1);
}
};