/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root)
{
return visit(root).balanced;
}
/////////////////////////
// Solution A: DFS
//
// By definition: depth of two subtrees never differ by more than 1.
private Result visit(TreeNode node)
{
if (node == null)
return new Result(0, true);
Result left = visit(node.left);
if (!left.balanced)
return new Result(0, false);
Result right = visit(node.right);
if (!right.balanced)
return new Result(0, false);
int height = Math.max(left.height, right.height) + 1;
boolean balanced = Math.abs(left.height - right.height) <= 1;
return new Result(height, balanced);
}
private static class Result
{
int height;
boolean balanced;
Result(int height, boolean balanced)
{
this.height = height;
this.balanced = balanced;
}
}
}