判断二叉树是否为平衡二叉树？树形DP，树形动态规划的递归套路

提示：本节开始，重点说二叉树的DP递归套路，非常重要而且容易理解

文章目录

• 判断二叉树是否为平衡二叉树？树形DP，树形动态规划的递归套路
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、树形动态规划的递归套路：树形DP
• 三、判断二叉树是否为平衡二叉树
• 总结

题目

平衡的二叉树，意味着，左树高度h1和右树的高度h2的高度差<=1；叫平衡二叉树
给你一个二叉树，请你判断，该二叉树，是否为平衡二叉树？

一、审题

示例：

上面这个树，x的左右树高度差为0<=1故，是平衡的
下面这个就不行了

本题的二叉树节点，和树为：

public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }

    //构造一颗树，今后方便使用
    public static Node generateBinaryTree(){
        //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        //      8
        //     9
        Node head = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        head.left = n2;
        head.right = n3;
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n2.left = n4;
        n2.right = n5;
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        n3.left = n6;
        n3.right = n7;
        Node n8 = new Node(8);
        n4.left = n8;
        Node n9 = new Node(9);
        n8.left = n9;
        return head;
    }

二、树形动态规划的递归套路：树形DP

95%的二叉树动态规划问题，都可以用以下套路解决：
一、定义个信息类：Info
收集x左树和右树都有的信息（左右树都有哦，而不是针对某单独的左树或者右树），比如是否平衡？树的高度，总之就是有的信息，不管你是String还是Boolean还是Integer类型的信息。经常是要讨论与x有关，还是 与x无关。

二、树形DP递归套路： 来到x节点
1）base case：考虑叶节点应该返回的信息Info
2）先收集左树和右树的信息Info
3）综合2）整理x自己的信息，并返回；

三、从题目给的二叉树head开始求（2），得到了一个head的信息Info，找里面咱们要用的那个信息：比如是否平衡？返回它。

来，咱们举例说明：实践知真理！

三、判断二叉树是否为平衡二叉树

（1）定义个信息类：Info
收集x左树和右树都有的信息（左右树都有哦，而不是针对某单独的左树或者右树），比如是否平衡？树的高度，总之就是有的信息，不管你是String还是Boolean还是Integer类型的信息。

本题中，我们去x的子树，不管左右，都要问你这个树高度height是多少？
为啥要高度呢？因为我要拿去求高度差，确定我x这个树，是否平衡？
既然要确定x是否平衡，我且问你子树，你平衡吗？平衡这个信息也要收集
为啥要收集平衡性呢？如果我x左树平衡，右树平衡，那再看x左右高度差满足条件的话，OK，x平衡！
因此我们需要定义收集的信息类：

//定义我需要的信息Info
    public static class Info{
        public boolean isBalanced;
        public int height;
        public Info(int h, boolean isb){
            height = h;
            isBalanced = isb;
        }
    }

（2）树形DP递归套路： 来到x节点
1）base case：考虑叶节点应该返回的信息Info
2）先收集左树和右树的信息Info
3）综合2）整理x自己的信息，并返回；

本题中：来到x节点，我们要收集x的信息：public static Info process(Node x)
1）base case：考虑叶节点应该返回的信息Info
遇到叶节点的左右子是null，自然高度我0，也自然是平衡的，所以返回：

return new Info(0, true);//高度0，是平衡的二叉树

2）先收集左树和右树的信息Info
自然用递归收集信息：

//左右拿信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

3）综合2）整理x自己的信息，并返回
Info需要2条信息，高度和是否平衡嗯
——高度嘛，自然是左右树最高高度+1，就是x的高度

——是否平衡呢？之前说过，如果左树是平衡的，右树它也平衡了，我左右俩高度差也是<=1则我x整个树就是平衡的
为啥要三个条件同时满足？
你看看如果高度差<=1，但是左树或者右树有其一不平衡，整个树可都不叫平衡：
下面这个，虽然x的左右高度差OK，但是，右树本人不平衡，x就不平衡。

再有：如果左右都平衡了，但是左右树高度差不行，那不行

因此，整合信息时，需要仨条件同时满足
OK，咱们手撕这个递归整理信息的代码：

//定义递归函数
    public static Info process(Node head){
        //终止条件
        if (head == null) return new Info(0, true);//高度0，是平衡的二叉树
        //左右拿信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        //整合自己的信息
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;//高度是左右最高+1
        boolean isBalanced = false;//初始化
        if (leftInfo.isBalanced && rightInfo.isBalanced &&
        Math.abs(leftInfo.height - rightInfo.height) <= 1) isBalanced = true;
        //平衡二叉树的条件，左子右子平衡，而且两者高度差不超过1

        return new Info(height, isBalanced);//返回我的信息
    }

（3）从题目给的二叉树head开始求（2），得到了一个head的信息Info，找里面咱们要用的那个信息：比如是否平衡？
返回它。
如何调用呢？直接，收集head的信息，返回info，
info自带高度和平衡信息，咱们要平衡信息，这是本题要的结果

//如何调用
    public static boolean isBalanceBinaryTreeOrNot(Node head){
        if (head == null) return true;
        Info info = process(head);
        return info.isBalanced;//返回它是还是不是
    }

看看测试结果：

public static void test(){
        Node cur = generateBinaryTree();//造树，返回头结点
        boolean isBalanced = isBalanceBinaryTreeOrNot(cur);
        System.out.println(isBalanced);
    }

    public static void main(String[] args) {
        test();
    }

//树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        //      8
        //     9

结果：

false

总结

提示：重要经验：

1）树形DP递归套路，占了二叉树动态规划的95%，只要熟悉这个解题流程，一切都不在话下，只不过，要搞清楚你要收集啥信息，才能整合出节点x的信息。目标就是为了收集head的信息。
2）整合信息时，遇到叶节点该怎么返回，要同时满足哪些条件，才能得到x节点的信息，都要摸排清楚。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。