根据带左右子节点标识的先序遍历结果验证是否为二叉搜索树(BST)

我们需要验证给定的先序遍历结果对应的二叉树是否为二叉搜索树（BST）。输入为存储了二叉树先序遍历序列的文件，每个节点附带子节点情况标识，示例输入如下：

-2 3
-4 3
-5 0
-3 0
 2 3
 0 3
-1 0
 1 0
 5 1
 4 0

上述示例中，值为-2的节点同时拥有左右子节点，值为-5的节点没有子节点。

子节点标识规则 #

• 0：无任何子节点
• 1：仅存在右子节点
• 2：仅存在左子节点
• 3：同时存在左右子节点

固定节点结构体定义 #

不可修改的节点结构体定义如下：

typedef struct _Tnode {
   int key;
   int height;
   struct _Tnode *left;
   struct _Tnode *right;
} Tno

注：本示例对应的二叉树并非BST，构造出的树结构如下：

-2 
                          /    \
                        /        \
                      -4          2
                      / \        /  \
                    -5   -3     0    5
                               / \    \
                             -1   1    4

内容的提问来源于stack exchange，提问作者kharevbv