BST判定

[编程题]BST判定

热度指数：921 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值，且不同节点的键值互不相等。二分查找树成立的判定条件：

对任何非叶子节点A，如果A存在左子树，则A的键值大于其左子树所有节点的键值，且，如果A存在右子树，则A的键值小于其右子树所有节点的键值

输入描述:

第一行：根节点键值;

第二行开始，二叉树的结构，每行代表一组根节点与左右子节点的对应关系，-1代表空节点。格式：

根节点键值:左子节点键值|右子节点键值

例如，

5:3|-1

表示键值为5的节点，左子节点的键值为3,右子节点为空节点

假设：所有节点的键值非负，且不超过1023

输出描述:

判断结果，0表示输入不是二分查找树，1表示输入是二分查找树

示例1

输入

5
5:4|7
4:3|8
7:2|-1
3:-1|-1
8:-1|-1
2:-1|-1

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

#define INF 0x3F3F3F3F
#define IsValidBST(infos, key) __IsValidBST(infos, key, -INF, +INF)

// ========== 二叉树节点信息表 ========== 
typedef int Key;
typedef struct {
  Key key;
  Key l_child, r_child;
} BST_NODE_INFO, *INFO;
// ========== 二叉树节点信息表 ========== 

int __IsValidBST(INFO infos, Key key, Key low, Key high) {
  if (key == -1) return 1;
  return key > low && key < high
      && __IsValidBST(infos, (infos + key)->l_child, low, key)
      && __IsValidBST(infos, (infos + key)->r_child, key, high);
}

int main(const int argc, const char* const argv[]) {
  
  BST_NODE_INFO infos[1000];
  Key root_key;
  fscanf(stdin, "%d", &root_key);
  
  Key fa, l_ch, r_ch;
  while (fscanf(stdin, "%d:%d|%d", &fa, &l_ch, &r_ch) != EOF) {
    (infos + fa)->key = fa;
    (infos + fa)->l_child = l_ch;
    (infos + fa)->r_child = r_ch;
  }
     
  return fprintf(stdout, "%d\n", IsValidBST(infos, root_key)), 0;
}

发表于 2021-08-13 11:40:59 回复(0)