首页 > 代码库 > PAT 4-1 CheckBST[1]
PAT 4-1 CheckBST[1]
Given a binary tree, you are supposed to tell if it is a binary search tree. If the answer is yes, try to find the KK-th largest key, else try to find the height of the tree.
Format of function:
int CheckBST ( BinTree T, int K );
where BinTree
is defined as the following:
typedef struct TNode *BinTree;
struct TNode{
int Key;
BinTree Left;
BinTree Right;
};
The function CheckBST
is supposed to return the K
-th largest key if T
is a binary search tree; or if not, return the negative height of T
(for example, if the height is 55, you must return -5?5).
Here the height of a leaf node is defined to be 1. T
is not empty and all its keys are positive integers. K
is positive and is never more than the total number of nodes in the tree.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode *BinTree;
struct TNode{
int Key;
BinTree Left;
BinTree Right;
};
BinTree BuildTree(); /* details omitted */
int CheckBST ( BinTree T, int K );
int main()
{
BinTree T;
int K, out;
T = BuildTree();
scanf("%d", &K);
out = CheckBST(T, K);
if ( out < 0 )
printf("No. Height = %d\n", -out);
else
printf("Yes. Key = %d\n", out);
return 0;
}
/* 你的代码将被嵌在这里 */
Sample Input 1: (for the following tree)
4
Sample Output 1:
Yes. Key = 5
Sample Input 2: (for the following tree)
3
Sample Output 2:
No. Height = 3
解答
其实过这题一个是用广度优先求出高度,另一个是用堆栈实现中缀遍历然后检查是否为从小到大的顺序遍历,啊哈三种遍历的递归解和非递归解都很重要的啦。
int CheckBST ( BinTree T, int K ){ int level_index[1000], tmp[1000], i, j = 0, k =0, tail = 1, top = -1; BinTree Q[1000], Stack[1000]; Q[0] = T; level_index[j] = 0; for(i = 0; i < 100; i++){ if(NULL != Q[i]->Left){ Q[tail++] = Q[i]->Left; } if(NULL != Q[i]->Right){ Q[tail++] = Q[i]->Right; } if(i == level_index[j]&&level_index[j] != tail - 1){ level_index[++j] = tail - 1; } else if(i == level_index[j]&&level_index[j] == tail - 1){ break; } } while(-1 != top||NULL != T){ while(NULL != T){ Stack[++top] = T; T = T->Left; } T = Stack[top]; top--; tmp[k++] = T->Key; T = T->Right; } for(k = 0; k < i; k++){ if(tmp[k] >= tmp[k + 1]){ return -1 - j; } } return tmp[i + 1 - K]; }
PAT 4-1 CheckBST[1]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。