F (1164) : B DS二叉排序树_有效的二叉排序树

 

Description

给你一个二叉树，判断其是否是一个有效的二叉排序树。

有效的二叉排序树定义如下：

1. 结点的左子树只包含小于当前结点的数。

2. 结点的右子树只包含大于当前结点的数。

3. 所有左子树和右子树自身必须也是二叉排序树。

Input

第一行输入t，表示有t个二叉树。

第二行起，每一行首先输入n，接着输入n个整数，代表二叉树。

以此类推共输入t个二叉树。

数组形式的二叉树表示方法与题目：DS二叉树_伪层序遍历构建二叉树 相同，输入-1表示空结点。

Output

每一行输出当前二叉树是否为二叉排序树，若是，则输出true，否则输出false。

共输出t行。

Input

4
3 2 1 3
7 5 1 4 -1 -1 3 6
7 2 1 4 -1 -1 3 6
8 9 8 -1 7 -1 6 -1 5

Output

true
false
true
true

代码如下,难点在于两个，一个是非递归层次遍历建树，第二个是判断为有效的二叉排序树。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> // 使用 INT_MIN 来初始化 pre#define MAXN 1005typedef struct Node
{int data;struct Node *Lchild;struct Node *Rchild;
} Node;Node *Build_Level(int *a, int num)
{Node *ROOT = NULL; // 待会要把根节点返回Node *queue[MAXN]; // 队列int front = 0, rear = 0;int k = 0;int ch;ch = a[k];k++;if (ch != -1){Node *root = (Node *)malloc(sizeof(Node));root->data = ch;root->Lchild = NULL;root->Rchild = NULL;ROOT = root;queue[rear++] = ROOT;}while (front != rear && k < num){Node *s = queue[front];front++;ch = a[k];if (ch != -1 && k < num){Node *news = (Node *)malloc(sizeof(Node));news->data = ch;news->Lchild = NULL;news->Rchild = NULL;s->Lchild = news;queue[rear++] = news;}k++;ch = a[k];if (ch != -1 && k < num){Node *news = (Node *)malloc(sizeof(Node));news->data = ch;news->Lchild = NULL;news->Rchild = NULL;s->Rchild = news;queue[rear++] = news;}k++;}return ROOT;
}bool JudgeBst(Node *T, int *pre)
{ // 判断是否为 BSTif (T == NULL){return true;}if (!JudgeBst(T->Lchild, pre)){return false;}if (T->data < *pre){return false;}*pre = T->data;return JudgeBst(T->Rchild, pre);
}int main()
{int t;int sum;scanf("%d", &t);while (t--){scanf("%d", &sum);int *array = (int *)malloc(sizeof(int) * sum);for (int i = 0; i < sum; i++){scanf("%d", &array[i]);}Node *p = Build_Level(array, sum); // p 为根节点int pre = INT_MIN;                 // 初始化 pre 为负无穷printf("%s\n", (JudgeBst(p, &pre) ? "true" : "false"));free(array);}return 0;
}