Comment on page

110.Balanced-Binary-Tree

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.
​
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.

代码

Approach #1

public class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root) != -1;
}
​
private int maxDepth(TreeNode root) {
if (root == null) return 0;
​
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
}
​
return Math.max(left, right) + 1;
}
}

Approach #2 Top-down recursion

class Solution {
// Recursively obtain the height of a tree. An empty tree has -1 height
private int height(TreeNode root) {
// An empty tree has height -1
if (root == null) {
return -1;
}
return 1 + Math.max(height(root.left), height(root.right));
}
​
public boolean isBalanced(TreeNode root) {
// An empty tree satisfies the definition of a balanced tree
if (root == null) {
return true;
}
​
// Check if subtrees have height within 1. If they do, check if the
// subtrees are balanced
return Math.abs(height(root.left) - height(root.right)) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}
};

Approach #3 Bottom-up recursion

// Utility class to store information from recursive calls
final class TreeInfo {
public final int height;
public final boolean balanced;
​
public TreeInfo(int height, boolean balanced) {
this.height = height;
this.balanced = balanced;
}
}
​
class Solution {
// Return whether or not the tree at root is balanced while also storing
// the tree's height in a reference variable.
private TreeInfo isBalancedTreeHelper(TreeNode root) {
// An empty tree is balanced and has height = -1
if (root == null) {
return new TreeInfo(-1, true);
}
​
// Check subtrees to see if they are balanced.
TreeInfo left = isBalancedTreeHelper(root.left);
if (!left.balanced) {
return new TreeInfo(-1, false);
}
TreeInfo right = isBalancedTreeHelper(root.right);
if (!right.balanced) {
return new TreeInfo(-1, false);
}
​
// Use the height obtained from the recursive calls to
// determine if the current node is also balanced.
if (Math.abs(left.height - right.height) < 2) {
return new TreeInfo(Math.max(left.height, right.height) + 1, true);
}
return new TreeInfo(-1, false);
}
​
public boolean isBalanced(TreeNode root) {
return isBalancedTreeHelper(root).balanced;
}
};