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

Kubrnete
• 阅读 1550

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

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

点赞
收藏
评论区
推荐文章
22 22
3年前
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第12篇文章。1.2.3.4.5.6.7.8.9.10.1.是什么?二叉查找树(BinarySearchTree)必须满足以下特点:若左子树不为空,则左子树的所有结点值皆小于根结点值若右子树不为空,则右子树的所有结点值皆大于根结点值左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
Wesley13 Wesley13
2年前
PTA 是否同一棵二叉搜索树(25 分)
是否同一棵二叉搜索树(25 分)给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。输入格式:输入包含若干组测
Wesley13 Wesley13
2年前
PTA 7
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。输入格式:输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。输出格式:将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一
似梦清欢 似梦清欢
1年前
树与二叉树
二叉树层次建树二叉树(BinaryTree)是由有限个结点组成的集合,它或者为空集合,或者仅含一个根结点,或者由一个根结点和两棵互不相交的左、右子树组成。树为空即根节点为空。二叉树的基本形态如下图:a:空的二叉树,treeNULL。b:只有空节点的二叉树,
Wesley13 Wesley13
2年前
Java实现 LeetCode 814 二叉树剪枝 (遍历树)
814\.二叉树剪枝给定二叉树根结点root,此外树的每个结点的值要么是0,要么是1。返回移除了所有不包含1的子树的原二叉树。(节点X的子树为X本身,以及所有X的后代。)示例1:输入:\1,null,0,0,1\输出:\1,null,0,null,1\解释:
Stella981 Stella981
2年前
LeetCode(98): 验证二叉搜索树
Medium!题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/\
Wesley13 Wesley13
2年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Stella981 Stella981
2年前
LeetCode初级算法之树:98 验证二叉搜索树
01题目信息题目地址:https://leetcodecn.com/problems/validatebinarysearchtree/给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。
Wesley13 Wesley13
2年前
6.重建二叉树(代码未完成)
 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。!(https://static.oschina.net/uploads
Wesley13 Wesley13
2年前
98. 验证二叉搜索树
题目描述给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。输入:5/\14 /\ 
Kubrnete
Kubrnete
Lv1
共看明月应垂泪,一夜乡心五处同。
文章
10
粉丝
1
获赞
6