如何判断一颗树是二叉搜索树的(判断一棵树是不是二叉搜索树)

导语：如何判断一颗树是二叉搜索树

题目 validate-binary-search-tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.Both the left and right subtrees must also be binary search trees.

二叉树 ：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为 二叉排序树

思路1 递归中序遍历

1.1 观察 中序遍历结果

中序遍历结果 ： 是有序的 [1 2 3 ]

当ouput为1是 ok

但ouput为2是 2>1 和前面一个记录进行比较

但ouput为3是 3>2 和前面一个记录进行比较

判读一是否validate-binary-search-tree只要比较便利当前节点和上个节点就可以了

1.2 步骤1 遍历root节点的左子树

2 输出当前节点内容 var1 和遍历的上个节点var2 进行比较 如果var1 >var2 符合条件

3 遍历root节点的右子树

1.3 coding

解决办法

int preVal=-100;//中序遍历之后输出的第i-1节点

int culVal=0;//中序遍历之后输出的第i个节点

bool isFirst = false; //中序遍历是否开始

思路 2 非递归中序遍历

2.1 步骤

条件：stack有记录 ||ptr

1 利用stack保存访问第一个节点的记录(left)

2 如果当前ptr为NULl 出stack操作 然后比较大小

3 如果ptr的右子树存在 遍历 右子树

2.2 coing

问题2: 第一个节点不需要比较

当中顺遍历输出第一个节点时候不需要和前面的进行比较新增遍历标记bool isFirst = false; //中序遍历是否开始输出

问题3: 死循环

如果ptr是叶节点，if(ptr->right){ ptr=ptr->right;}else{ptr=NULL; //ptr已经遍历完毕完毕 避免重复插入ptr设置为NULL}

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请与我联系，一经查实立刻删除内容。本文内容由快快网络小媛创作整理编辑！