剑指offer第二版-55.2.平衡二叉树

本系列导航：剑指offer（第二版）java实现导航帖

面试题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