173. 二叉搜索树迭代器

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class BSTIterator {
  17.     List<Integer> pre;
  18.     Iterator<Integer> cur;
  19.     public BSTIterator(TreeNode root) {
  20.         pre = new ArrayList<>();
  21.         preorder(root, pre);
  22.         cur = pre.iterator();
  23.     }
  25.     public int next() {
  26.         return cur.next();
  27.     }
  29.     public boolean hasNext() {
  30.         return cur.hasNext();
  31.     }
  33.     private void preorder(TreeNode root, List<Integer> pre) {
  34.         if (root == null)
  35.             return;
  37.         preorder(root.left, pre);
  38.         pre.add(root.val);
  39.         preorder(root.right, pre);
  40.     }
  41. }
  43. /**
  44.  * Your BSTIterator object will be instantiated and called as such:
  45.  * BSTIterator obj = new BSTIterator(root);
  46.  * int param_1 = obj.next();
  47.  * boolean param_2 = obj.hasNext();
  48.  */