题目描述:
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,
- 其左子树中所有结点的键值小于该结点的键值;
- 其右子树中所有结点的键值大于等于该结点的键值;
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式:
输入的第一行给出正整数N(<=1000)。随后一行给出N个整数键值,其间以空格分隔。
输出格式:
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出“YES”,然后在下一行输出该树后序遍历的结果。数字间有1个空格,一行的首尾不得有多余空格。若答案是否,则输出“NO”。
输入样例1:7 8 6 5 7 10 8 11输出样例1:
YES 5 7 6 8 11 10 8输入样例2:
7 8 10 11 8 6 7 5输出样例2:
YES 11 8 10 7 5 6 8输入样例3:
7 8 6 8 5 10 9 11输出样例3:
NO
思路:
纯暴力,求出本身的先序,在求出翻转的先序,比较,判断就可以了。
注意点就是:
开辟的空间问题,要开辟两个空间,因为本身需要一个节点,翻转需要一个节点,(开辟一个的话,地址块只有一个,指针会多次被改变,从而结果错误。)
代码如下:
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; struct node { int value; struct node *rchild; struct node *lchild; node() { rchild = lchild = NULL; } }; int flag,ff,nodeNumber,TreeNode[1005]; void buildTree(node *head,node *temp) { int k = head->value; int t = temp->value; if(k > t) { if(head->lchild == NULL) { head->lchild = temp; return ; } buildTree(head->lchild,temp); } else { if(head->rchild == NULL) { head->rchild = temp; return ; } buildTree(head->rchild,temp); } return ; } void buildTree_flip(node *head,node *temp) { int k = head->value; int t = temp->value; if(k <= t) { if(head->lchild == NULL) { head->lchild = temp; return ; } buildTree_flip(head->lchild,temp); } else { if(head->rchild == NULL) { head->rchild = temp; return ; } buildTree_flip(head->rchild,temp); } return ; } void preorder(node *head) { if(head == NULL) return ; if(head->value !=TreeNode[nodeNumber]) { flag = 1; return ; } nodeNumber++; if(head->lchild != NULL) preorder(head->lchild); if(head->rchild != NULL) preorder(head->rchild); } int main() { int n,t; scanf("%d",&n); scanf("%d",&TreeNode[0]); ///初始化头节点 struct node *x1 = new node(); x1->value = TreeNode[0]; struct node *x2 = new node(); x2->value = TreeNode[0]; ///开始建造树 for(int i=1; i<n; i++) { scanf("%d",&TreeNode[i]); ///注意点:开辟空间要是两个,不然指向同一个空间,指针会乱。 node *temp1 = new node(); temp1->value = TreeNode[i]; node *temp2 = new node(); temp2->value = TreeNode[i]; buildTree_flip(x2,temp2); buildTree(x1,temp1); } ///第一次与本身比较,判断是不是 flag = 0; nodeNumber=0; preorder(x1); if(flag == 0) { printf("YES\n"); ff=0; hoxu(x1); printf("\n"); } else { ///第二次与flip比较,判断是不是翻转的树 flag = 0 nodeNumber=0; preorder(x2); if(flag == 0) { printf("YES\n"); ff=0; hoxu(x2); printf("\n"); } else { printf("NO\n"); } } return 0; }