110平衡二叉树

平衡二叉树

https://leetcode-cn.com/problems/balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

public class BalanceTree {
    public boolean isBalanced(TreeNode root){
        //只需返回根节点的Info类的isBalance信息即可
        return process(root).isBalance;
    }
    //因为需要左子树的两个信息（左子树是否平衡，左子树的高度），右子树也需要这两个信息。因此，将这两个信息封装成一个Info类。
    public static class Info{
        Boolean isBalance;
        int height;
        public Info(Boolean isBalance,int height){
            this.isBalance=isBalance;
            this.height=height;
        }
    }
    public Info process(TreeNode root){
        //如果root为null，是一棵平衡树，而且高度为0；
        if(root==null){
            return new Info(true,0);
        }
        //获取左子树的信息节点。
        Info left=process(root.left);
        //获取右子树的信息节点
        Info right=process(root.right);
        //通过左右子树的信息，判断根节点是否平衡。
        Boolean isBalance=left.isBalance&&right.isBalance&&(Math.abs(left.height-right.height)<2);
        //通过左右子树的信息，判断根节点的高度。
        int height=Math.max(left.height,right.height)+1;
        //返回根节点的信息。
        return new Info(isBalance,height);
    }
}

总结

1.当使用递归，需要知道子树的多个信息时，可以将多个信息封装成一个类。将类作为方法的返回值，进行连接。