很锻炼DP/recursive思路的一道题，个人感觉DP/recursive算是比较难写的题目了。这道题解法的巧妙之处在于巧用-1，并且使用临时存储，节省了很多开支。这道题同时也在Career Cup上面出现过
这道题我两次调试通过，第一次错是因为input{}, output false, expected true
我的算法只有一层递归(因为巧用-1的原因)，runs in O(N) time, andO(H) space
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public boolean isBalanced(TreeNode root) { 12 if(root==null) return true; 13 int leftheight=getheight(root.left); 14 int rightheight=getheight(root.right); 15 if(leftheight==-1 || rightheight==-1) return false; 16 if(Math.abs(leftheight-rightheight)>1) return false; 17 else return true; 18 } 19 public int getheight(TreeNode root){ 20 if(root==null) return 0; 21 int leftheight=getheight(root.left); 22 int rightheight=getheight(root.right); 23 if(leftheight==-1) return -1; 24 if(rightheight==-1) return -1; 25 if(Math.abs(leftheight-rightheight)>1) return -1; 26 return Math.max(leftheight, rightheight)+1; 27 } 28 }
别人的solutions: 都有两层递归，isBalanced()一层递归，同时isBalanced()中调用height(), height()又是一层递归，时间复杂度为O(N^2), 不如我的方法优越
Solution1:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public boolean isBalanced(TreeNode root) { 12 // Start typing your Java solution below 13 // DO NOT write main() function 14 15 16 if(root == null) return true; 17 int leftSubtreeHeight = height(root.left); 18 int rightSubtreeHeight = height(root.right); 19 return Math.abs(leftSubtreeHeight-rightSubtreeHeight)<=1 && 20 isBalanced(root.left) && isBalanced(root.right); 21 } 22 23 public int height(TreeNode node){ 24 if(node ==null) return 0; 25 26 return 1+Math.max(height(node.left),height(node.right)); 27 } 28 29 30 }
Solution2:
1 public class BalancedBianryTree { 2 public boolean isBalanced(TreeNode root) { 3 // Start typing your Java solution below 4 // DO NOT write main() function 5 if(root==null){ 6 return true; 7 } 8 int diff = Math.abs(getHeight(root.left)-getHeight(root.right)); 9 if(diff>1){ 10 return false; 11 } 12 return isBalanced(root.left)||isBalanced(root.right); 13 14 } 15 public int getHeight(TreeNode root){ 16 if(root==null){ 17 return 0; 18 } 19 int leftHeight = getHeight(root.left); 20 int rightHeight = getHeight(root.right); 21 return Math.max(leftHeight,rightHeight)+1; 22 } 23 24 25 }
Leetcode: Balanced Binary Tree,布布扣,bubuko.com
Leetcode: Balanced Binary Tree
原文：http://www.cnblogs.com/EdwardLiu/p/3704786.html