給定一棵二叉樹的頭節點head，回傳這顆二叉樹是不是滿二叉樹
特點：如果一顆二叉樹的有L層，結點個數是N個的話，必定滿足以下這個公式：
(2^L)-1 == N，且只有滿二叉樹有這個特點
根據二叉樹的遞回套路，以及滿二叉樹的特點，我們向每顆子樹要的資訊就是高度和結點個數，比較簡單，就不贅述了，直接看代碼叭：
package com.harrison.class08;
public class Code05_IsFull {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class Info{
public int height;
public int nodes;
public Info(int h,int n) {
height=h;
nodes=n;
}
}
public static Info process1(Node head) {
if(head==null) {
return new Info(0, 0);
}
Info leftInfo=process1(head.left);
Info righInfo=process1(head.right);
int height=Math.max(leftInfo.height, righInfo.height)+1;
int nodes=leftInfo.nodes+righInfo.nodes+1;
return new Info(height, nodes);
}
public static boolean isFull1(Node head) {
if(head==null) {
return true;
}
Info allInfo=process1(head);
return (1<<allInfo.height)-1==allInfo.nodes;
}
public static int h(Node head) {
if (head == null) {
return 0;
}
return Math.max(h(head.left), h(head.right)) + 1;
}
public static int n(Node head) {
if (head == null) {
return 0;
}
return n(head.left) + n(head.right) + 1;
}
public static boolean isFull2(Node head) {
if (head == null) {
return true;
}
int height = h(head);
int nodes = n(head);
return (1 << height) - 1 == nodes;
}
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
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 = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isFull1(head) != isFull2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/381980.html
標籤：其他