二叉树题集(持续更新中)

Kubrnete 等级 1099 1 0
标签: Java

对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。

1. 求二叉搜索树最大深度

输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。

输入样例:8 6 8 5 10 9 11 0

输出样例:4

常规的求二叉搜索树深度的做法是递归到叶子结点往上求深度,对每个父节点求其左右子树的最大深度,即

private int deep(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int leftdeep = deep(node.left);
            int rightdeep = deep(node.right);

            return Math.max(leftdeep, rightdeep) + 1;
        }
    }

而这题实际上可以在建树的过程中对每个结点求深度,最终遍历出最大深度。完整代码如下

public class TreeTest {
    public static int depth = 0;   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t;
        Node root = null;
        while ((t = in.nextInt()) != 0) {
            root = create(root, t, 1);
        }
        System.out.println(depth);
    }

    public static Node create(Node root, int data, int d) {

        if (root == null) {
            if (d > depth) depth = d;
            return new Node(data, null, null, d);
        }
        if (data < root.data) root.left = create(root.left, data, d + 1);
        else root.right = create(root.right, data, d + 1);
        return root;
    }
}

class Node {
    public Node(int data, Node left, Node right, int d) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.d = d;
    }

    int data;
    int d;
    Node left;
    Node right;
}

2. 搜索树判断

题目描述

如果我们交换每个节点的左子树和右子树,得到的树叫做镜像二叉搜索树。现在我们给出一个整数键值序列,请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,如果是,则输出对应二叉树的后序遍历序列。

输入格式:输入的第一行包含一个正整数N(≤1000),第二行包含N个整数,为给出的整数键值序列,数字间以空格分隔。

输出格式:输出的第一行首先给出判断结果,如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,则输出YES,否侧输出NO。如果判断结果是YES,下一行输出对应二叉树的后序遍历序列。数字间以空格分隔,行尾不能有多余的空格。

输入样例

7
8 6 8 5 10 9 11

输出样例:NO

输入样例

7
8 6 5 7 10 8 11

输出样例

YES
5 7 6 8 11 10 8
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int data;
    Node *left = NULL;
    Node *right = NULL;
    Node(int d) : data(d) {}
} * Tree;
Tree tree = NULL;
void create(Tree &tree, int data)
{
    if (!tree)
    {
        tree = new Node(data);
        return;
    }
    if (data < tree->data)
        create(tree->left, data);
    else
        create(tree->right, data);
}
void rcreate(Tree &tree, int data)
{
    if (!tree)
    {
        tree = new Node(data);
        return;
    }
    if (data < tree->data)
        rcreate(tree->right, data);
    else
        rcreate(tree->left, data);
}

int n, a[1005], b[1005], cnt = 0;
void preOrder(Tree root)
{
    if (root == NULL)
        return;
    b[cnt++] = root->data;
    preOrder(root->left);
    preOrder(root->right);
}
void postOrder(Tree root, int flag)
{
    if (root == NULL)
        return;
    if (flag == 1)
    {
        postOrder(root->left, flag);
        postOrder(root->right, flag);
    }
    else
    {
        postOrder(root->right, flag);
        postOrder(root->left, flag);
    }
    cout << root->data;
    if (root != tree)
        cout << " ";
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        create(tree, a[i]); //根减而治之,递归建树
    preOrder(tree);
    int flag = 0;
    if (equal(begin(a), end(a), begin(b), end(b)))
        flag = 1;
    if (!flag)
    {
        Tree tree = NULL;
        cnt = 0;
        for (int i = 0; i < n; i++)
            rcreate(tree, a[i]);
        preOrder(tree);
        if (equal(begin(a), end(a), begin(b), end(b)))
            flag = 2;
    }
    if (flag)
    {
        cout << "YES" << endl;
        postOrder(tree, flag);
    }
    else
        cout << "NO";
}

本文转自 https://blog.csdn.net/guanguandaren/article/details/108687374,如有侵权,请联系删除。

收藏
评论区

相关推荐

二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。 1\. 求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8 6 8 5 10 9 11 0输出样例:4常规的求二叉搜索树深度的做法是递
作为一个码农终于把这些笔记看懂了,牛皮轰轰
Spring面试高频问题 SpringMVC面试高频问题 MyBatis面试高频问题 SpringBoot面试高频题 SpringCloud面试高频问题 Redis高级面试题 Dubbo高频常问面试问题 Java虚拟机(JVM) MySQL数据库高频面试问题 Java高频面试专题合集解析:当然在这还有更多整理总结的Java进阶学习笔记和面试题未展示,在这也是
JAVA NIO 字符集编码问题
字符集是非英语国家人最头疼的事情,尤其是样样有国标的中国。所以本朝的码农比洋大人程序员学各种技能都要多会一个技能点——应付编码问题。 NIO我们同样需要面对编码解码问题。 * 六、字符集:CharSet * 编码:字符串 -> 字节数组 * 解码:字节数组 -> 字符串 有哪些编码呢? @Test p
Java中多个集合的交集,并集和差集
一、交集   java中交集使用 A.retainAll(B) ,交集的结果在集合A中。 1 import org.junit.Test; 2 3 import java.util.HashSet; 4 import java.util.Set; 5 6 /** 7 * 交集
Java中的Map集合
Map接口简介 ------- Map接口是一种双列集合,它的每个元素都包含一个键对象Key和值对象Value,键和值对象之间存在一种对应关系,称为映射。从Map集合中访问元素时,只要指定了Key,就能找到对应的Value, Map中的键必须是唯一的,不能重复,如果存储了相同的键,后存储的值会覆盖原有的值,简而言之就是键相同,值覆盖。 **Map常用
Java中的集合
Java Collections Framework是Java编程语言的核心部分之一。集合几乎用于任何编程语言中。大多数编程语言都支持各种类型的集合,例如List, Set, Queue, Stack等。 ### 1.什么是Java Collections Framework? 集合就像容器一样,将多个项目组合在一个单元中。例如,一罐巧克力,一组名称等。
Java中的集合框架
上一篇[《Java中的集合框架-Map》](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.cnblogs.com%2Fzw971084570%2Fp%2F10125362.html)把集合框架中的键值对容器Map中常用的知识记录了一下,本节记录一下集合框架的两个工具类Collec
Java多线程面试问题集锦
如果你即将去一家从事大型系统研发的公司进行Java面试,不可避免的会有多线程相关的问题。下面是一些针对初学者或者新手的问题,如果你已经具备良好的基础,那么你可以跳过本文,直接尝试针对进阶水平的Java多线程编程问题及解答。 关联链接: [Java multi-threading-1](https://www.oschina.net/action/GoToL
Java程序员集合框架面试题
Java集合框架是最常被问到的Java面试问题,要理解Java技术强大特性,就有必要掌握集合框架。这里有一些实用问题,常在Java面试中问到。 **1、 什么是Java集合API** Java集合框架API是用来表示和操作集合的统一框架,它包含接口、实现类、以及帮助[程序员](https://www.oschina.net/action/GoToLink
Java集合面试题
**Collection** Set和hashCode以及equals方法的联系 Set内存放的元素为什么不可以重复,内部是如何保证和实现的? List 和 Set 区别 List 和 Map 区别 Arraylist 与 LinkedList 区别 ArrayList 与 Vector 区别 Arraylist与LinkedList默认空间是
Java面试题全集(中)
这部分主要是与Java Web和Web Service相关的面试题。 96、阐述Servlet和CGI的区别? 答:Servlet与CGI的区别在于Servlet处于服务器进程中,它通过多线程方式运行其service()方法,一个实例可以服务于多个请求,并且其实例一般不会销毁,而CGI对每个请求都产生新的进程,服务完成后就销毁,所以效率上低于Servl
2020年1
#前言 2020年一半儿快要过去了,总结了上半年各类Java面试题,初中级和中高级都有,包括Java OOP面试题、Java集合/泛型面试题、Java异常面试题、Java种的IO与NIO面试题、Java反射面试题、Java序列化面试题、Java注解面试题、多线程与并发面试题、JVM面试题、MySQL面试题、Redis面试题、Memcached面试题、Mo
2021预备春招:Java面试必看的999道面试解析,助你通过大厂面试拿到满意offer
2021预备春招:Java面试必看的999道面试解析,助你通过大厂面试. **前言:** 本文收集整理了各大厂常见面试题N道,你想要的这里都有内容涵盖:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Memcached、Redis、MySQL、Spring、Spring Boot、Spring Cloud、Rab
2021预备春招:Java面试必看的999道面试解析,助你通过大厂面试拿到满意offer
2021预备春招:Java面试必看的999道面试解析,助你通过大厂面试. **前言:** 本文收集整理了各大厂常见面试题N道,你想要的这里都有内容涵盖:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Memcached、Redis、MySQL、Spring、Spring Boot、Spring Cloud、Rab
TinyScript语言介绍
许多的人使用Java来作为主要的编程语言,许多的时候感觉代码太过繁复,当然有Scala、Kotlin、Python等等语言号称可以解决此问题,但是毕竟生态圈的切换不是个小问题。同时语法结构和Java相去甚远也导致切换的成本毕竟高。 为此本人做了一下尝试,准备走一个中间路线,主题还是用Java语言,但是在需要的时候用TinyScript来解决一下问题,然后再