1. 题目描述
判断二叉树是不是完全二叉树
2. 测试案例
- 树空
- 树不空
3. 最佳思路
3.1 笔试
- 启示：
当不知道如何解题时，可以找不同，将整个树，拆分成不同的组成模块。然后观察各个模块，找突破口。- 细节：
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
System.out.println(right(root));
}
// 判断一颗树是否为完全二叉树(利用层次遍历)
public static boolean right(Node root) {
if (root == null) // 边界条件
return true;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
boolean isFindBorder = false;
while (!queue.isEmpty()) {
/* 1. 出一个元素 */
Node cur = queue.poll();
/* 2. 将所出元素的左右孩子加入队列 */
if (cur.left != null)
queue.offer(cur.left);
if (cur.right != null)
queue.offer(cur.right);
/* 3.判断是否为完全二叉树 */
if (cur.left == null && cur.right != null) // 一个必要条件:只要某节点有右孩子而没有左孩子，则其一定不为完全二叉树
return false;
// (1)有左右孩子的跳过
if (!isFindBorder && cur.left != null && cur.right != null)
continue;
// (2)途中若遇到有左孩子但无右孩子 或 没有左孩子的也没有右孩子的，则后序结点全是叶结点
if (isFindBorder && (cur.left != null || cur.right != null))
return false;
if (cur.right == null) // 找到边界
isFindBorder = true;
}
return true;
}
}
3.2 面试
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
static class Info {
public boolean isCBT; // 是否是完全二叉树
public boolean isFBT; // 是否是满二叉树
public int height; // 树高
public Info(boolean isCBT, boolean isFBT, int height) {
this.isCBT = isCBT;
this.isFBT = isFBT;
this.height = height;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
System.out.println(isCompleteBinaryTree(root));
}
// 判断一颗树是否为完全二叉树
public static boolean isCompleteBinaryTree(Node root) {
return pos(root).isCBT;
}
// 使用递归后序遍历解题
public static Info pos(Node cur) {
/* 0. 边界条件 */
if (cur == null)
return new Info(true, true, 0);
/* 1. 获取左右子树信息 */
Info leftInfo = pos(cur.left);
Info rightInfo = pos(cur.right);
/* 2. 实例化当前结点的Info对象，将info对象的信息设置正确，并返回该对象 */
// (1)实例化了info对象，并设置了height
Info info = new Info(false, false, Math.max(leftInfo.height, rightInfo.height) + 1);
// (2)设置isFBT
if (leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height)
info.isFBT = true;
// (3)设置isCBT
if (leftInfo.isFBT && rightInfo.isFBT
&& (leftInfo.height == rightInfo.height || leftInfo.height - rightInfo.height == 1))
info.isCBT = true;
if ((!leftInfo.isFBT && leftInfo.isCBT) && rightInfo.isFBT
&& (leftInfo.height - rightInfo.height == 1))
info.isCBT = true;
if (leftInfo.isFBT && (!rightInfo.isFBT && rightInfo.isCBT)
&& (leftInfo.height == rightInfo.height))
info.isCBT = true;
return info;
}
}
4. 代码
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
static class Info {
public boolean isCBT; // 是否是完全二叉树
public boolean isFBT; // 是否是满二叉树
public int height; // 树高
public Info(boolean isCBT, boolean isFBT, int height) {
this.isCBT = isCBT;
this.isFBT = isFBT;
this.height = height;
}
}
public static void main(String[] args) {
int testCount = 10000000;
int maxHeight = 100;
int maxValue = 50;
boolean isSucceed = true;
for (int i = 0; i < testCount; i++) {
// 生成样本
Node root = creatRandomBT(maxHeight, maxValue);
// 判断两种方式结果是否相同
boolean ans1 = right(root);
boolean ans2 = isCompleteBinaryTree(root);
if (ans1 != ans2) { // 不相同
isSucceed = false;
printBT(root, 0, 7, "根:");
System.out.println("right方法的结果:" + ans1);
System.out.println("isCompleteBinaryTree方法的结果:" + ans2);
break;
}
}
System.out.println(isSucceed ? "nice!" : "fuck!");
}
// 打印二叉树
public static void printBT(Node cur, int height, int len, String flag) {
// 边界条件
if (cur == null)
return;
// 右
printBT(cur.right, height + 1, len, "R:");
// 根
printNode(cur, height, len, flag);
// 左
printBT(cur.left, height + 1, len, "L:");
}
public static void printNode(Node cur, int height, int len, String flag) {
StringBuffer str = new StringBuffer(height * (len + 1));
// 添加前空格
for (int i = 0; i < height * len; i++) {
str.append(" ");
}
String valueStr = flag + String.valueOf(cur.value);
int leftSpaces = len - valueStr.length() >> 2;
int rightSpaces = len - valueStr.length() - leftSpaces;
// 添加左空格
for (int i = 0; i < leftSpaces; i++) {
str.append(" ");
}
// 添加数值
str.append(valueStr);
// 添加右空格
for (int i = 0; i < rightSpaces; i++) {
str.append(" ");
}
System.out.println(str);
}
// 随机创建二叉树
public static Node creatRandomBT(int maxHeight, int maxValue) {
return randomBT((int)(Math.random() * (maxHeight + 1)), maxValue); // 确定高度
}
// 利用先序遍历生成二叉树
public static Node randomBT(int height, int maxValue) {
// 边界条件
if (height <= 0)
return null;
// 等概率判断是否创建该结点
Node cur = null;
if (Math.random() > 0.5) { // 等概率的true和false。如果为true，说明该结点存在
// 根
cur = new Node((int) (Math.random() * (maxValue + 1)));
// 左
cur.left = randomBT(height - 1, maxValue);
// 右
cur.right = randomBT(height - 1, maxValue);
}
return cur;
}
// 判断一颗树是否为完全二叉树(利用层次遍历)
public static boolean right(Node root) {
if (root == null) // 边界条件
return true;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
boolean isFindBorder = false;
while (!queue.isEmpty()) {
/* 1. 出一个元素 */
Node cur = queue.poll();
/* 2. 将所出元素的左右孩子加入队列 */
if (cur.left != null)
queue.offer(cur.left);
if (cur.right != null)
queue.offer(cur.right);
/* 3.判断是否为完全二叉树 */
if (cur.left == null && cur.right != null) // 一个必要条件:只要某节点有右孩子而没有左孩子，则其一定不为完全二叉树
return false;
// (1)有左右孩子的跳过
if (!isFindBorder && cur.left != null && cur.right != null)
continue;
// (2)途中若遇到有左孩子但无右孩子 或 没有左孩子的也没有右孩子的，则后序结点全是叶结点
if (isFindBorder && (cur.left != null || cur.right != null))
return false;
if (cur.right == null) // 找到边界
isFindBorder = true;
}
return true;
}
// 判断一颗树是否为完全二叉树
public static boolean isCompleteBinaryTree(Node root) {
return pos(root).isCBT;
}
// 使用递归后序遍历解题
public static Info pos(Node cur) {
/* 0. 边界条件 */
if (cur == null)
return new Info(true, true, 0);
/* 1. 获取左右子树信息 */
Info leftInfo = pos(cur.left);
Info rightInfo = pos(cur.right);
/* 2. 实例化当前结点的Info对象，将info对象的信息设置正确，并返回该对象 */
// (1)实例化了info对象，并设置了height
Info info = new Info(false, false, Math.max(leftInfo.height, rightInfo.height) + 1);
// (2)设置isFBT
if (leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height)
info.isFBT = true;
// (3)设置isCBT
if (leftInfo.isFBT && rightInfo.isFBT
&& (leftInfo.height == rightInfo.height || leftInfo.height - rightInfo.height == 1))
info.isCBT = true;
if ((!leftInfo.isFBT && leftInfo.isCBT) && rightInfo.isFBT
&& (leftInfo.height - rightInfo.height == 1))
info.isCBT = true;
if (leftInfo.isFBT && (!rightInfo.isFBT && rightInfo.isCBT)
&& (leftInfo.height == rightInfo.height))
info.isCBT = true;
return info;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84577.html
