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

题目
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
  }