【剑指offer系列之二叉树】判断是否为平衡二叉树

题目：

平衡二叉树的性质为：要么是一颗空树，要么任何一个节点的左右子树高度差的绝对值不超过1。给定一棵二叉树的头结点head，判断这棵二叉树是否为平衡二叉树。要求时间复杂度为O(N)

思路：

采用后序遍历。对于任何节点，先遍历其左子树，并用depth[ ]数组保存遍历的深度，同时返回该节点是否为平衡二叉树，如果不是，整棵树退出遍历，直接返回false；如果是，则遍历右子树。

public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return isBalance(root,new int[1]); } public boolean isBalance(TreeNode root,int []depth){ if(root==null){ depth[0]=0; return true; } boolean left=isBalance(root.left,depth); int leftdepth=depth[0]; boolean right=isBalance(root.right,depth); int rightdepth=depth[0]; depth[0]=Math.max(leftdepth+1,rightdepth+1); if(left&&right&&Math.abs(leftdepth-rightdepth)<=1)return true; return false; } }