题解 | #判断二叉树是否为平衡二叉树#

import java.io.*;
import java.util.*;

public class Main {

    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int data){
            this.value=data;
        }
    }

    /*判断二叉树是否是平衡二叉树
    树形dp问题
    第1步：以某个节点X为头节点，分析答案可能情况
        可能1：X左子树不平衡，则以X为头节点的树不平衡
        可能2：X右子树不平衡，则以X为头节点的树不平衡
        可能3：X的左右子树高度差大于1，则以X为头节点的树不平衡
        可能4：上面都没有，以X为头节点的树平衡
    第2步：根据可能性分析，列出所有需要的信息。左右子树都需要知道各自是否平衡，以及高度
    第3步：根据第2步信息汇总，定义ReturnType类
    * */
    public static class ReturnType{
        public boolean isBalanced;
        public int height;

        public ReturnType(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    /*第4步：设计递归函数。递归函数是处理以X为头节点的情况下的***括设计递归的base case,
    默认直接得到左树、右树所有信息，以及把可能性整合，返回到第3步信息结构这四个小步骤
    * */
    public static ReturnType process(Node head){
        if(head==null){
            return new ReturnType(true,0);
        }
        ReturnType leftData=process(head.left);
        ReturnType rightData=process(head.right);

        int height=Math.max(leftData.height, rightData.height)+1;
        boolean isBalanced=leftData.isBalanced&& rightData.isBalanced
                && Math.abs(leftData.height- rightData.height)<2;

        return  new ReturnType(isBalanced,height);
    }

    public static boolean isBalanced(Node head){
        return process(head).isBalanced;
    }

    public static Node createTree(Scanner in, int n){
        int rootValue=in.nextInt();
        Node root=new Node(rootValue);
        HashSet<Node> set=new HashSet<Node>();
        set.add(root);

        //n行读取
        for (int i = 0; i < n; i++) {
            int fatherValue= in.nextInt();
            int leftValue=in.nextInt();
            int rightValue=in.nextInt();
            //遍历
            for (Node e:set){
                //1、比较节点
                if(e.value==fatherValue){
                    //2、建立左右节点
                    Node left= leftValue==0?null:new Node(leftValue);
                    Node right= rightValue==0?null:new Node(rightValue);
                    e.left=left;
                    e.right=right;
                    //3、放入节点
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }


        return root;
    }
    /*
    in:3 1
        1 2 3
        2 0 0
        3 0 0
    out:true
    * */
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Node root=createTree(in,n);

        boolean result=isBalanced(root);
        System.out.println(result);
    }
}