验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

  1. /*中序遍历将所有元素升序输出*/
  3. class Solution {
  5.     Stack<TreeNode> s;
  6.     int last;
  7.     boolean flag = true;
  9.     Solution(){
  10.         s = new Stack<TreeNode>();
  11.     }
  13.     public boolean trans(TreeNode root){
  15.         while(root != null || !s.isEmpty()){
  16.             while(root != null){
  17.                 s.add(root);
  18.                 root = root.left;
  19.             }
  20.             if(!s.isEmpty()){
  21.                 root = s.pop();
  22.                 if(!flag){
  23.                     if(last >= root.val)
  24.                         return false;
  25.                     last = root.val;
  26.                 }
  27.                 else{
  28.                     last = root.val;
  29.                     flag = !flag;
  30.                 }
  31.                 root = root.right;
  32.             }
  33.         }
  34.         return true;
  35.     }
  37.     public boolean isValidBST(TreeNode root) {
  38.         return trans(root);
  39.     }
  40. }

二叉搜索树迭代器

https://leetcode-cn.com/problems/binary-search-tree-iterator/

  1. class BSTIterator {
  3.     Stack<TreeNode> s;
  4.     TreeNode root;
  6.     public BSTIterator(TreeNode root) {
  7.         s = new Stack<TreeNode>();
  8.         this.root = root;
  9.     }
  11.     public int next() {
  13.         while(root != null){
  14.             s.add(root);
  15.             root = root.left;
  16.         }
  18.         root = s.pop();
  19.         int r = root.val;
  20.         root = root.right;
  21.         return r;
  23.     }
  25.     public boolean hasNext() {
  26.         return (root != null || !s.isEmpty());
  27.     }
  28. }