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

Kubrnete
• 阅读 1243

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

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

点赞
收藏
评论区
推荐文章
技术小男生 技术小男生
4个月前
linux环境jdk环境变量配置
1:编辑系统配置文件vi/etc/profile2:按字母键i进入编辑模式,在最底部添加内容:JAVAHOME/opt/jdk1.8.0152CLASSPATH.:$JAVAHOME/lib/dt.jar:$JAVAHOME/lib/tools.jarPATH$JAVAHOME/bin:$PATH3:生效配置
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
22 22
1年前
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第12篇文章。1.2.3.4.5.6.7.8.9.10.1.是什么?二叉查找树(BinarySearchTree)必须满足以下特点:若左子树不为空,则左子树的所有结点值皆小于根结点值若右子树不为空,则右子树的所有结点值皆大于根结点值左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
22 22
1年前
线索二叉树的原理及创建
【系列推荐阅读】1.为什么要用到线索二叉树?我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树(链式存储方式):乍一看,会不会有一种违和感?整个结构一共有7个结点,总共14个指针域,其中却有8个指针域都是空的。对于一颗有n个结点的二叉树而言,总共会有n1个空指针域,这个规律使用所有的二叉树。这么多的空指针域是不
Stella981 Stella981
1年前
B+树原理以及Java代码实现
最初查找二叉树,由于树的高度会随着有序序列输入而急剧增长,后来出现平衡二叉树,红黑树。B树可以海量数据的快速查询检索,B树主要分为B树(B树),B树,B\树等。B树(B树)M路搜索树,参数M定义节点的分支个数;对于根节点孩子数目为\2,M\,对于其余节点孩子数目为\M/2,M\;每个节点含有关键字属性,至少M/21
Wesley13 Wesley13
1年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先,二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为:根节点左子树右子树中序遍历为:左子树根节点右子树后序遍历为:左子树右子树根节点(只要记住根节点在哪里就是什么遍历,且都是先左再右)线索化现在有这么一棵二叉树,它的数据结
Wesley13 Wesley13
1年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Wesley13 Wesley13
1年前
04.重建二叉树 (Java)
题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。(https://www.oschina.net/action/GoToLink?urlht
Stella981 Stella981
1年前
LeetCode 235. 二叉搜索树的最近公共祖先
原文链接: LeetCode235.二叉搜索树的最近公共祖先(https://my.oschina.net/ahaoboy/blog/3118052)给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最近公共祖先表示为一个结点x,满足x是p、q的祖先且x
Wesley13 Wesley13
1年前
6.重建二叉树(代码未完成)
 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。!(https://static.oschina.net/uploads
Suzhou Suzhou
2个月前
树与二叉树
二叉树层次建树二叉树(BinaryTree)是由有限个结点组成的集合,它或者为空集合,或者仅含一个根结点,或者由一个根结点和两棵互不相交的左、右子树组成。树为空即根节点为空。二叉树的基本形态如下图:a:空的二叉树,treeNULL。b:只有空节点的二叉树,
Kubrnete
Kubrnete
Lv1
共看明月应垂泪,一夜乡心五处同。
10
文章
1
粉丝
6
获赞