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

Kubrnete 等级 615 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,如有侵权,请联系删除。

收藏
评论区

相关推荐

List集合
Java的List集合 一、ArrayList 1.插入 java / 在元素序列尾部插入 / public boolean add(E e) { // 1. 检测是否需要扩容 ensureCapacityInternal(size 1); // Increments modCount // 2. 将新元素插入序列尾
Groovy 集合与闭包
Groovy 集合 在 Groovy 提供的所有方便的快捷方式和功能中,最有帮助的一个可能就是内置的 集合。回想一下在 Java 编程中是如何使用集合的 — 导入 java.util 类,初始化集合,将项加入集合。这三个步骤都会增加不少代码。 而 Groovy 可以直接在语言内使用集合。在 Groovy 中,不需要导入专门的类,也不需要初始化对象。集合是语
java传值和传引用问题
这个问题还是很常见的,如果你平常敲代码比较多你可能经常会遇到这个问题。如果你知道java这个机制,你可能还会一直在找代码的问题。java中的值传递和引用传递。比如下面有这俩个方法java private void updataValue(String s){ s "123"; } private void upd
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。 1\. 求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8 6 8 5 10 9 11 0输出样例:4常规的求二叉搜索树深度的做法是递
完全背包问题
问题描述 有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v\i\,体积为w\i\,求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可
操作系统-简答题-合集
操作系统简答题合集 (一) 操作系统引论 1. 简述操作系统的功能?答: 操作系统是计算机资源的管理者。主要有处理机管理、存储管理、设备管理、文件管理。此外,操作系统还为用户提供使用操作系统硬件系统的接口,分别是命令接口、程序接口、图形接口。操作系统的四个基本特征是并发、共享、异步、虚拟。 2. 解释以下术语:资源、多道程序
使用jsp直接执行定时任务
使用jsp直接执行定时任务servicehtml<%@ page import"com.leasing.emogo.framework.util.ApplicationContextUtils" %<%@ page import"job.dsc.GetInfoByAssetPackageJob" %<%@ page contentType
Java集合之综合论述
1.Java集合 1.1 集合应用场景1. 无法预测存储数据的数量的情况下,2. 同时存储一对一关系的数据3. 需要进行数据的增删4. 数据重复问题 1.2 集合框架的体系结构 集合框架分为两类,一是Collection,用于存储类的对象。二是Map,以键值对的形式存储信息。 Collection主要有三个子接口,List(序列),Queue(队列
Java中集合排序常用的方式
1. 集合排序概述 1.1 集合排序的主要内容: 集合中的级别数据类型排序 集合中的字符串排序 Comparator接口 Comparable接口 1.2 数组排序回顾 int[] arr12,25,22,17,89,22;Arrays.sort(arr);输出:12,17,22,22,25,89Java的Arrays类中有一个sort()方法,该方法是Ar
Java练习(三)——返回集合中的最大的和最小的元素
题目:在一个列表中存储以下元素:apple,grape,banana,pear,现要求将集合进行排序,返回集合中的最大的和最小的元素,并将排序后的结果打印在控制台上,要求的打印输出方法分别为默认toString输出、迭代器输出、for循环遍历输出和增强for循环输出。 package test;import java.util.;public class P
cpu分析利器 — async-profiler
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 简介asyncprofiler是一款采集分析java性能的工具,翻译一下github上的项目介绍:asyncprofiler是一款没有Safepoint bias problem的低开销java采集分析器,它利用HotSpot特殊的api来收集栈信息以及
秋招已经开始准备了!【Java面试题】最新Java开发岗面试知识笔记
在最近两个月不断的面试中,我分类总结了 Java 开发岗位面试中的一些知识点。主要包括以下几个部分: 1. Java 基础知识点 2. Java 常见集合 3. 高并发编程(JUC 包) 4. JVM 内存管理 5. Java 8 知识点 6. 网络协议相关 7. 数据库相关 8. MVC 框架相关 9. 大数据相关 10. Linux 命令相关面试,
阿里面试被问到【垃圾回收器】,不会怎么办??
垃圾回收器 GC 分类与性能指标 垃圾回收器概述1. 垃圾收集器没有在规范中进行过多的规定,可以由不同的厂商、不同版本的JVM来实现。2. 由于JDK的版本处于高速迭代过程中,因此Java发展至今已经衍生了众多的GC版本。3. 从不同角度分析垃圾收集器,可以将GC分为不同的类型。Java不同版本新特性1. 语法层面:Lambda表达式、switch、
【垃圾回收】全面解析,内含面试题及图文详解!!
垃圾回收概述和相关算法1. Java 和 C++语言的区别,就在于垃圾收集技术和内存动态分配上,C++语言没有垃圾收集技术,需要程序员手动的收集。2. 垃圾收集,不是Java语言的伴生产物。早在1960年,第一门开始使用内存动态分配和垃圾收集技术的Lisp语言诞生。3. 关于垃圾收集有三个经典问题: 哪些内存需要回收? 什么时候
作为一个码农终于把这些笔记看懂了,牛皮轰轰
Spring面试高频问题 SpringMVC面试高频问题 MyBatis面试高频问题 SpringBoot面试高频题 SpringCloud面试高频问题 Redis高级面试题 Dubbo高频常问面试问题 Java虚拟机(JVM) MySQL数据库高频面试问题 Java高频面试专题合集解析:当然在这还有更多整理总结的Java进阶学习笔记和面试题未展示,在这也是