[编程题]判断一棵二叉树是否为搜索二叉树和完全二叉树
- 热度指数：2460 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。
输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
ps:节点的标号就是节点的值
输出描述:
第一行输出该二叉树是否为搜索二叉树的答案，如果是则输出 "true"，否则输出 "false"。
第二行输出该二叉树是否为完全二叉树的答案，如果是则输出 "true"，否则输出 "false"。
示例1
输入
3 2 2 1 3 1 0 0 3 0 0
输出
true true
备注:
import java.util.*;
public class Main{
public static int preValue = Integer.MIN_VALUE;
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left) {
this.val = val;
this.left = left;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
TreeNode root=new TreeNode(x);
Queue<TreeNode> que=new LinkedList<>();
que.add(root);
HashMap<Integer,TreeNode> map=new HashMap<>();
map.put(root.val,root);
for(int i=0;i<n;i++){
int fa=sc.nextInt();
int l=sc.nextInt();
int r=sc.nextInt();
if(l!=0){
map.get(fa).left=new TreeNode(l);
map.put(l,map.get(fa).left);
}
if(r!=0){
map.get(fa).right=new TreeNode(r);
map.put(r,map.get(fa).right);
}
}
System.out.println(isBST1(root));
System.out.println(isCBT(root));
}
//使用中序遍历的方法改编,此方法适用head.val的值范围为Integer.MIN_VALUE<head.val<=Integer.MAX_VALUE；等于Integer.MIN_VALUE需要继续优化，
public static boolean isBST1(TreeNode head) {
if (head == null) {
return true;
}
boolean isleft = isBST1(head.left);
if (!isleft) {
return false;
} else {
if (head.val <= preValue) {
return false;
} else {
preValue = head.val;
}
}
return isBST1(head.right);
}
public static boolean isCBT(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
boolean key = false; //key用来指示第一次遇见了左右孩子不双全的情况没
while (!que.isEmpty()) {
int n = que.size();
for (int i = 0; i < n; i++) { //层序遍历
TreeNode node = que.poll();
if (node.left == null && node.right != null) {
return false;
}
//在key变换后，表示出现的节点只能是叶子节点
if (key) {
if (node.left != null || node.right != null) {
return false;
}
}
//第一次出现左右孩子不双全，改变key
if (node.right == null) {
key = true;
}
//往队列里面加节点
if (node.left != null) {
que.add(node.left);
}
if (node.right != null) {
que.add(node.right);
}
}
}
return true;
}
}
发表于 2022-07-10 20:28:59
回复(0)
二叉搜索树直接检验中序遍历序列的单调递增性即可。完全二叉树采用层次遍历的方式检验，如果遇到有右孩子没有左孩子的节点，不是完全二叉树；如果遇到一个左右孩子不双全的节点，那之后遍历的所有节点都应该是叶子节点，不满足就不是完全二叉树。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 构建二叉树
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
TreeNode root = new TreeNode(Integer.parseInt(params[1]));
HashMap<Integer, TreeNode> map = new HashMap<>();
map.put(root.val, root);
for(int i = 0; i < n; i++){
params = br.readLine().split(" ");
int val = Integer.parseInt(params[0]);
int leftVal = Integer.parseInt(params[1]);
int rightVal = Integer.parseInt(params[2]);
TreeNode node = map.get(val);
if(leftVal != 0) {
node.left = new TreeNode(leftVal);
map.put(leftVal, node.left);
}
if(rightVal != 0) {
node.right = new TreeNode(rightVal);
map.put(rightVal, node.right);
}
}
// 判断二叉搜索树
System.out.println(isBST(root));
// 判断完全二叉树
System.out.println(isCBT(root));
}
private static boolean isBST(TreeNode root) {
int prev = Integer.MIN_VALUE;
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
if(root.val <= prev) return false; // 破坏了中序遍历的单调递增特性，直接返回false
else prev = root.val;
root = root.right;
}
}
return true;
}
private static boolean isCBT(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean flag = false; // 孩子不双全的节点是否出现过
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node.left == null && node.right != null) return false; // 有右孩子没有左孩子
if((node.left != null || node.right != null) && flag) return false; // 出现过左右孩子不双全的节点，之后必须全部是叶子节点
if(node.left == null || node.right == null) flag = true; // 遇到左右孩子不双全的节点
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
return true;
}
}
发表于 2021-11-14 13:56:24
回复(0)
分享下我在牛客做《程序员代码面试指南》中树相关试题时构建树的方法，也就是将输入转换成树，方便使用，因为这类不少，都要构建树。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
/*
private static TreeNode buildTree(Scanner sc, int n, int rootVal) {
Map<Integer, TreeNode> map = new HashMap<>();
while (n-- > 0) {
int fa = sc.nextInt();
int lch = sc.nextInt();
int rch = sc.nextInt();
TreeNode faNode = map.get(fa);
if (faNode == null) {
faNode = new TreeNode(fa);
map.put(fa, faNode);
}
if (lch != 0) {
TreeNode lchNode = map.get(lch);
if (lchNode == null) {
lchNode = new TreeNode(lch);
map.put(lch, lchNode);
}
faNode.left = lchNode;
}
if (rch != 0) {
TreeNode rchNode = map.get(rch);
if (rchNode == null) {
rchNode = new TreeNode(rch);
map.put(rch, rchNode);
}
faNode.right = rchNode;
}
}
return map.get(rootVal);
}
*/ import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int rootVal = sc.nextInt();
TreeNode root = buildTree(sc, n, rootVal);
System.out.println(isBST(root, new int[]{Integer.MIN_VALUE}));
System.out.println(isCompleteBinaryTree(root));
}
private static boolean isCompleteBinaryTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while(!que.isEmpty()) {
int sz = que.size();
for (int i = 0; i < sz; ++i) {
TreeNode node = que.poll();
if (node.left != null && node.right != null) {
que.add(node.left);
que.add(node.right);
} else {
if (node.left == null && node.right != null) {
return false;
}
if (node.left != null) {
que.add(node.left);
}
while(!que.isEmpty()) {
TreeNode vnode = que.poll();
if (vnode.left != null || vnode.right != null) {
return false;
}
}
break;
}
}
}
return true;
}
private static boolean isBST(TreeNode root, int[] pre) {
if (root == null) {
return true;
}
if (!isBST(root.left, pre)) {
return false;
}
if (pre[0] > root.val) {
return false;
}
pre[0] = root.val;
return isBST(root.right, pre);
}
private static TreeNode buildTree(Scanner sc, int n, int rootVal) {
Map<Integer, TreeNode> map = new HashMap<>();
while (n-- > 0) {
int fa = sc.nextInt();
int lch = sc.nextInt();
int rch = sc.nextInt();
TreeNode faNode = map.get(fa);
if (faNode == null) {
faNode = new TreeNode(fa);
map.put(fa, faNode);
}
if (lch != 0) {
TreeNode lchNode = map.get(lch);
if (lchNode == null) {
lchNode = new TreeNode(lch);
map.put(lch, lchNode);
}
faNode.left = lchNode;
}
if (rch != 0) {
TreeNode rchNode = map.get(rch);
if (rchNode == null) {
rchNode = new TreeNode(rch);
map.put(rch, rchNode);
}
faNode.right = rchNode;
}
}
return map.get(rootVal);
}
}
发表于 2021-08-14 20:40:59
回复(0)
import java.util.*;
class node {
int val;
node left, right;
node(int val) {
this.val = val;
}
}
public class Main {
private static int pre = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
node root = new node(scanner.nextInt());
HashMap<Integer, node> map = new HashMap<>();
map.put(root.val, root);
for(int i=0;i<n;i++) {
node parent, left, right;
parent = getNodeIfExist(map, scanner.nextInt());
left = getNodeIfExist(map, scanner.nextInt());
right = getNodeIfExist(map, scanner.nextInt());
parent.left = left;
parent.right = right;
}
System.out.println(isBST(root));
System.out.println(isCBT(root));
}
private static boolean isBST(node root) {
//是否二叉搜索树
if(root == null) return true;
boolean left = isBST(root.left);
if(left) {
if(pre > root.val) return false;
pre = root.val;
}
return left && isBST(root.right);
}
private static boolean isCBT(node root) {
//是否完全二叉树
if(root == null) return true;
Queue<node> queue = new LinkedList<>();
queue.add(root);
boolean leaf = false;
while(queue.size() != 0) {
node head = queue.remove();
if(head.right != null && head.left == null) return false;
if(head.left != null && head.right == null) {
if(leaf) return false;
leaf = true;
}
if(head.left != null) {
queue.add(head.left);
}
if (head.right != null) {
queue.add(head.right);
}
}
return true;
}
private static node getNodeIfExist(HashMap<Integer, node> map, int val) {
if(val == 0) return null;
if(map.get(val) == null) {
map.put(val, new node(val));
}
return map.get(val);
}
} 第一步是建树，因为节点的值是唯一的，所以用hashmap。这样可以O1时间get到节点。
第一问BST, 中序遍历是升序的，记录前一个的值，保证升序就行。
第二问CBT，区分满二叉树和完全二叉树，满二叉树是每一层都填满，完全二叉树是满二叉树层序遍历又缺少了连续的尾部。层序遍历中，某个节点 有右没有左->肯定不行；有左没有右->只能有一次，之后都必须是左右都没有。
发表于 2019-09-24 16:42:01
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-19 17:35:09
-
2022-09-08 09:34:57 -
2022-09-02 20:48:48 -
2022-08-21 10:05:59 -
2022-08-19 10:35:49
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
