幼稚的我

参考链接

二叉搜索树

基本结构体

typedef struct BTNode{
    int data;
    BTNode *lchild;
    BTNode *rchild;
}*BSTree;

利用引用建树

void InsertBST(BSTree &T,int x)
{
    if(!T)
    {
        BSTree S=new BTNode;
        S->data=x;
        S->lchild=S->rchild=NULL;
        T=S;
    }
    else if(x<T->data)
        InsertBST(T->lchild,x);
    else if(x>=T->data)
        InsertBST(T->rchild,x);
}

二叉搜索树的中序遍历

//二叉搜索树的中序遍历是一个单调递增的序列。
//利用这个特性可以判断一个一个二叉树是否是搜索树。
//N是结点数，In数组存放中序遍历结果
int In[N];
int i=0;
void InOrder(BSTree T)	//root	数组的话就是找根节点root
{
    if(T)		//root!=-1
    {
    	InOrder(T->lchild);
    	In[i++]=T->data;
    	InOrder(T->rchild);
    }
}

//在main函数里面判断In序列是否单调递增
bool flag=true;
for(int t=1;t<N;++t)
{
    if(In[t]<=In[t-1])
    {
        flag=false;
        break;
    }
}

利用二叉搜索树的特性，其中序遍历是递增的特点来判断其是否是一颗二叉搜索树

leetcode解法

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // If next element in inorder traversal
      // is smaller than the previous one
      // that's not BST.
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

更多解法

• 递归

class Solution {
  public boolean helper(TreeNode node, Integer lower, Integer upper) {
    if (node == null) return true;

    int val = node.val;
    if (lower != null && val <= lower) return false;
    if (upper != null && val >= upper) return false;

    if (! helper(node.right, val, upper)) return false;
    if (! helper(node.left, lower, val)) return false;
    return true;
  }

  public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 迭代

class Solution {
  LinkedList<TreeNode> stack = new LinkedList();
  LinkedList<Integer> uppers = new LinkedList(),
          lowers = new LinkedList();

  public void update(TreeNode root, Integer lower, Integer upper) {
    stack.add(root);
    lowers.add(lower);
    uppers.add(upper);
  }

  public boolean isValidBST(TreeNode root) {
    Integer lower = null, upper = null, val;
    update(root, lower, upper);

    while (!stack.isEmpty()) {
      root = stack.poll();
      lower = lowers.poll();
      upper = uppers.poll();

      if (root == null) continue;
      val = root.val;
      if (lower != null && val <= lower) return false;
      if (upper != null && val >= upper) return false;
      update(root.right, val, upper);
      update(root.left, lower, val);
    }
    return true;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。