判断二叉树是否为满二叉树

冰露可乐

2024-03-29 帮助1人

判断二叉树是否为满二叉树？

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

二叉树的动态规划树形DP递归套路系列文章有这些，可以帮助你快速掌握树形DP的题目解题思想，就一个套路：
（1）判断二叉树是否为平衡二叉树？树形DP，树形动态规划的递归套路
（2）求二叉树中，任意两个节点之间的距离最大值是多少
（3）求二叉树中，包含的最大二叉搜索子树的节点数量是多少
（4）求公司派对的最大快乐值

题目

给你一颗二叉树head，请你判断二叉树是否为满二叉树？
所谓完全满二叉树
二叉树的节点数量N与二叉树的层数k满足下列关系：
N = 2^(k) - 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
        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);
        Node n8 = new Node(8);
        n3.left = n6;
        n3.right = n7;
        n4.right = n8;
        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，找里面咱们要用的那个信息：比如是否平衡？返回它。

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

三、解题思路：

根据题意，咱们只需要求二叉树的层数k和二叉树的节点数N
故，每次去一个x开头的树，需要收集k和N

public static class Info{
        public int height;
        public int num;
        public Info(int h, int n){
            height = h;
            num = n;
        }
    }

二、树形DP递归套路： 来到x节点
设定f(Node x)为来到x节点，要收集x开头的树，总的节点数N和层数k、

1）base case：考虑叶节点应该返回的信息Info
来到叶节点的null时，节点为0个，层数为0
返回的信息Info(0,0)

2）先收集左树和右树的信息Info
收集左右很简单

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

3）综合2）整理x自己的信息，并返回；
——层数是多少？自然是左边层数与右边层数最大值 1（x自己）；
——总结点个数？自然是左边节点右边节点数 1（x自己）

手撕代码很简单：

//复习：收集x下整个树的节点数N和层数k
    public static Info f(Node x){
        if (x == null) return new Info(0, 0);//高0，无节点

        //左右收信息
        Info left = f(x.left);
        Info right = f(x.right);

        //整理x的信息
        int height = Math.max(left.height, right.height)   1;
        int N = left.num   right.num   1;
        
        return new Info(height, N);
    }

三、从题目给的二叉树head开始求（2），得到了一个head的信息Info，找里面咱们要用的那个信息：比如是否平衡？返回它。
如何调用呢？
直接拿头节点head的k和N
判断公式是否成立就行：
注意：1<<x=2^x
这是位运算的强大之处

//调用
    public static boolean isFBT(Node head){
        if (head == null) return true;
        
        Info info = f(head);
        
        return info.num == (1 << info.height) - 1;
    }

测试结果：

//构造一颗树，今后方便使用
    public static Node generateBinaryTree2(){
        //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        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);
        Node n8 = new Node(8);
        n3.left = n6;
        n3.right = n7;
        //n4.right = n8;
        return head;
    }

    public static void test(){
    //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        //      8
        Node cur = generateBinaryTree();//搞一棵树来
        boolean isFBT = isFullBinaryTree(cur);
        System.out.println(isFBT);

//树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        cur = generateBinaryTree2();//搞一棵树来
        isFBT = isFBT(cur);
        System.out.println(isFBT);
    }

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

false
true

总结

提示：重要经验：

1）非常非常典型的二叉树DP递归套路，收集信息，整理信息，往上传，最后找到head的信息，判断整个二叉树的条件
2）记住满二叉树的条件是满足公式：节点数N和层数的k关系严格符合：N=2^k-1
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。

这篇好文章是转载于：学新通技术网

判断二叉树是否为满二叉树