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 depth of the two subtrees of every node never differ by more than 1. /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // Exceed time limit public class Solution { public boolean isBalanced(TreeNode root) { if(root==null) return true; int lh = height(root.left); int rh = height(root.right); if(Math.abs(lh-rh)>1) return false; return isBalanced(root.left) && isBalanced(root.right); } public int height(TreeNode node) { if(node==null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } } ///////////////////////////////////////////////////////////////////////////////// //优化后的方法为：对于每一个节点，我们递归获得左右子树的深度，如果子树是平衡的，则返回真实的深度，若不平衡，直接返回-1 public class Solution { public boolean isBalanced(TreeNode root) { if(balanced(root)>=0) return true; else return false; } public int balanced(TreeNode node) { if(node==null) return 0; int l = balanced(node.left); if(l==-1) return -1; int r = balanced(node.right); if(r==-1) return -1; if(Math.abs(l-r)>1) return -1; else return 1 + Math.max(l, r); } }