二叉树题集(持续更新中) - HelloWorld开发者社区

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

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