面试题55.2：平衡二叉树
题目要求：
输入二叉树的根节点，判断该树是否是平衡二叉树。如果某二叉树的任意节点的左右子树深度之差不超过1，则该树是平衡二叉树。
解题思路：
思路1：依据平衡二叉树的定义解决。借助于上一题二叉树的深度，从根节点开始逐点判断树的左右子树的深度差值是否满足要求。由于此解法是从根到叶的判断，每一次获取节点有需要从当前节点遍历到叶节点，因此需要多次遍历。
思路2：如果用后序遍历，那么访问某一个节点时已经访问了它的左右子树。同时，在访问节点时记录下它的深度，并由左右子树的深度推出父亲节点的深度，这样我们就能通过遍历一遍完成整棵树的平衡性判断。
对于某一个子树，需要给出它的平衡性的判断，还要给出它的深度，此处我将平衡性的判断作为返回值，深度通过长度为1的数组传递出去，见boolean isBalanced2Core(TreeNode<Integer> node,int[] depth)。
package chapter6;
import structure.TreeNode;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/17
* Time : 10:03
* Description:平衡二叉树
**/
public class P273_isBalanced {
//借助于深度，判断是否是平衡二叉树,由于是从根到叶逐点判断，需要多次遍历树
public static boolean isBalanced(TreeNode<Integer> node){
if(node==null)
return true;
int left = treeDepth(node.left);
int right = treeDepth(node.right);
int diff = left - right;
if(diff<-1||diff>1)
return false;
return isBalanced(node.left)&&isBalanced(node.right);
}
public static int treeDepth(TreeNode<Integer> root){
if(root==null)
return 0;
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left>right?(left+1):(right+1);
}
//用后序遍历，并记录每个节点的深度，从而可以通过一次遍历完成整棵树的判断
public static boolean isBalanced2(TreeNode<Integer> node){
if(node==null)
return true;
return isBalanced2Core(node,new int[]{0});
}
public static boolean isBalanced2Core(TreeNode<Integer> node,int[] depth){
if(node==null){
depth[0] = 0;
return true;
}
int[] left = new int[]{0};
int[] right = new int[]{0};
if(isBalanced2Core(node.left,left)&&isBalanced2Core(node.right,right)){
int diff = left[0]-right[0];
if(diff<=1&&diff>=-1){
depth[0] = 1+(left[0]>right[0]?left[0]:right[0]);
return true;
}
else
return false;
}
return false;
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(1);
root.left = new TreeNode<>(2);
root.left.left = new TreeNode<>(4);
root.left.right = new TreeNode<>(5);
root.left.right.left = new TreeNode<>(7);
root.right = new TreeNode<>(3);
root.right.right = new TreeNode<>(6);
System.out.println(isBalanced(root));
System.out.println(isBalanced2(root));
}
}
运行结果
true
true
