Thinking process I - Brute Force Top down
left subtree is balanced
right subtree is balanced
the tree whose root is current node is balanced
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
Thinking process II - Bottom up
if left subtree is not balanced, return -1. Same as the right subtree.
if both left and right subtree is balanced, then check whether currently is balanced
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = getDepth(root.left);
if (leftDepth == -1) return -1;
int rightDepth = getDepth(root.right);
if (rightDepth == -1) return -1;
return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1;
}
}