【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.
思路：
最简单的思路是遍历每个节点，计算每个节点的左右子树的高度差是否不超过1，一般树的问题都会用到递归，所以这中算法是方法一，这里两个函数都用了迭代，isbanlanced（）迭代树的每个节点，depth（）来迭代计算每个节点的左右子树高度差，这个算法双重迭代时间复杂度是O（N*N），效率很低。
方法二也用了迭代，这里是不等计算出所有节点的高度差来判断，利用DFS深度优先算法计算的时候，一旦节点的左右高度差超多2，则返回false，这样算法的复杂度就是O（N）
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ //way 1 ： O（N*N）： public class Solution { public boolean isBalanced(TreeNode root) {//recursive the node if(root==null)return true; int leftDepth = depth(root.left); int rightDepth = depth(root.right); return Math.abs(leftDepth-rightDepth)<=1&&isBalanced(root.left)&&isBalanced(root.right); } public int depth(TreeNode node){//recursive the depth of each node if(node==null)return 0; else return Math.max(depth(node.left),depth(node.right))+1; } }
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ //way 2: O(N) public class Solution { public boolean isBalanced(TreeNode root) { return judgeRootValue(root) != -1; } int judgeRootValue(TreeNode root){ if(root==null) return 0; int leftDepth = judgeRootValue(root.left); int rightDepth = judgeRootValue(root.right); //these two lines following are to judge if the subNode(leftNode,rightNode) is banlanced or not if(leftDepth==-1)return -1; if(rightDepth==-1)return -1; //the line following is to judge if the rootNode is banlanced or not if(Math.abs(leftDepth-rightDepth)>1) return -1; return Math.max(leftDepth,rightDepth)+1; } }
原文：http://www.cnblogs.com/lucky-star-star/p/5022336.html