vlambda博客
学习文章列表

剑指offer——平衡二叉树

题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
 
平衡二叉树:如果二叉树的每个节点的左子树和右子树的深度不大于1,它就是平衡二叉树。首先直接能想到的是先求左右子树的高度,查看是否平衡:
 
   
   
 
  
    
    
  
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root == null){ return true; } if(Math.abs(getDepth(root.left) - getDepth(root.right)) > 1){ return false; } else { return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } }public int getDepth(TreeNode root) { if(root == null){ return 0; }int left = getDepth(root.left); int right = getDepth(root.right); return Math.max(left,right) + 1; } }
但是这样有一点不太好的地方,就是增加了很多不必要的遍历,每次都要算深度。因此加以改进:
  
    
    
  
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return getDepth(root) != -1; } private int getDepth(TreeNode root) { if (root == null) return 0; int left = getDepth(root.left); if (left == -1) return -1; int right = getDepth(root.right); if (right == -1) return -1; return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right); } }