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

1、题目

给定一棵二叉树的根节点，判断这棵二叉树是否为满二叉树。

2、分析

满二叉树：如果树的高度是 $h$，则节点数一定是 $2^h-1$。

所以根据二叉树的递归套路：假设X为根节点的树，向左右子树收集两个信息：高度 $h$ 和 节点数 $n$，判断是否满足满二叉树的条件。

另外，如果左树是满二叉树，右树是满二叉树，且左右树的高度一致，那么整棵树是满二叉树。

所以，也可以利用二叉树的递归套路，从左右树获取信息：（1）是否为满二叉树 （2）高度

3、实现

C++版

/* > File Name: 036.判断二叉树是否为满二叉树.cpp > Author: Maureen > Mail: > Created Time: 五 7/ 1 16:37:02 2022 / #include  
     #include  
     using namespace std; class TreeNode { 
    public: int value; TreeNode *left; TreeNode *right; TreeNode(int data) : value(data) { 
   } }; //方法1：收集整棵树的高度和节点数  //只有满二叉树满足：2^h - 1 == n class Info1 { 
    public: int height;//高度 int nodeCnt;//节点数 Info1(int h, int c) : height(h), nodeCnt(c) { 
   } }; Info1 *process1(TreeNode *x) { 
    if (x == nullptr) { 
    return new Info1(0, 0); } Info1 *leftInfo = process1(x->left); Info1 *rightInfo = process1(x->right); int height = max(leftInfo->height, rightInfo->height) + 1; int nodeCnt = leftInfo->nodeCnt + rightInfo->nodeCnt + 1; return new Info1(height, nodeCnt); } bool isFullBT1(TreeNode *root) { 
    if (root == nullptr) return true; Info1 *info = process1(root); return (1 << info->height) - 1 == info->nodeCnt; } //方法2: 收集 子树是否满二叉树 和 子树高度  //左树满 && 右树满 && 左树高度和右树高度一样，那么整棵树就是满的 class Info2 { 
    public: bool isFull; int height; Info2(bool isfull, int h) : isFull(isfull), height(h) { 
   } }; Info2 *process2(TreeNode *x) { 
    if (x == nullptr) { 
    return new Info2(true, 0); } Info2 *leftInfo = process2(x->left); Info2 *rightInfo = process2(x->right); int height = max(leftInfo->height, rightInfo->height) + 1; bool isFull = leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height; return new Info2(isFull, height); } bool isFullBT2(TreeNode *root) { 
    return process2(root)->isFull; } //for test  TreeNode *generate(int level, int maxl, int maxv) { 
    if (level > maxl || (rand() % 100 / (double)101) < 0.5) return nullptr; TreeNode *root = new TreeNode(rand() % maxv); root->left = generate(level + 1, maxl, maxv); root->right = generate(level + 1, maxl, maxv); return root; } TreeNode *generateRandomBST(int level, int value) { 
    return generate(1, level, value); } int main() { 
    srand(time(0)); int level = 5; int value = 100; int testTimes = ; cout << "Test begin:" << endl; for (int i = 0; i < testTimes; i++) { 
    TreeNode *root = generateRandomBST(level, value); if (isFullBT1(root) != isFullBT2(root)) { 
    cout << "Failed!" << endl; return 0; } } cout << "Success!" << endl; return 0; } 

Java 版

public class isFullBT { 
    public static class Node { 
    public int value; public Node left; public Node right; public Node(int data) { 
    this.value = data; } } // 第一种方法 // 收集整棵树的高度h，和节点数n // 只有满二叉树满足 : 2 ^ h - 1 == n public static boolean isFull1(Node head) { 
    if (head == null) { 
    return true; } Info1 all = process1(head); return (1 << all.height) - 1 == all.nodes; } public static class Info1 { 
    public int height; //高度 public int nodes; //节点数 public Info1(int h, int n) { 
    height = h; nodes = n; } } public static Info1 process1(Node head) { 
    if (head == null) { 
    return new Info1(0, 0); } Info1 leftInfo = process1(head.left); Info1 rightInfo = process1(head.right); int height = Math.max(leftInfo.height, rightInfo.height) + 1; int nodes = leftInfo.nodes + rightInfo.nodes + 1; return new Info1(height, nodes); } // 第二种方法 // 收集子树是否是满二叉树 // 收集子树的高度 // 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的 public static boolean isFull2(Node head) { 
    if (head == null) { 
    return true; } return process2(head).isFull; } public static class Info2 { 
    public boolean isFull; public int height; public Info2(boolean f, int h) { 
    isFull = f; height = h; } } public static Info2 process2(Node h) { 
    if (h == null) { 
    return new Info2(true, 0); } Info2 leftInfo = process2(h.left); Info2 rightInfo = process2(h.right); boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height; int height = Math.max(leftInfo.height, rightInfo.height) + 1; return new Info2(isFull, height); } // for test public static Node generateRandomBST(int maxLevel, int maxValue) { 
    return generate(1, maxLevel, maxValue); } // for test public static Node generate(int level, int maxLevel, int maxValue) { 
    if (level > maxLevel || Math.random() < 0.5) { 
    return null; } Node head = new Node((int) (Math.random() * maxValue)); head.left = generate(level + 1, maxLevel, maxValue); head.right = generate(level + 1, maxLevel, maxValue); return head; } public static void main(String[] args) { 
    int maxLevel = 5; int maxValue = 100; int testTimes = ; System.out.println("测试开始"); for (int i = 0; i < testTimes; i++) { 
    Node head = generateRandomBST(maxLevel, maxValue); if (isFull1(head) != isFull2(head)) { 
    System.out.println("出错了!"); } } System.out.println("测试结束"); } }