110.Balanced-Binary-Tree
110. Balanced Binary Tree
题目地址
https://leetcode.com/problems/balanced-binary-tree/
http://www.lintcode.com/problem/balanced-binary-tree/
http://www.jiuzhang.com/solutions/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;
}
};
Last updated