思路

非递归中序遍历二叉树 —> 用栈存储

1) 构造器 —> 将根结点的最左结点都压栈

2) hashNext() —> 等价于判断栈是否为空

3) next()

  1. 访问结点。
  2. 处理其右子树的结点。
    • 将以右子树为根的最左结点都压栈。

实现

  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. public class BSTIterator {
  18.     private Stack<TreeNode> stack = new Stack<>();
  20.     public BSTIterator(TreeNode root) {
  21.         TreeNode t = root;
  22.         while(t != null) {
  23.             stack.push(t);
  24.             t = t.left;
  25.         }
  26.     }
  28.     public int next() {
  29.         TreeNode cur = stack.pop();
  30.         int value = cur.val;
  31.         cur = cur.right;
  32.         // 每次访问完一个node，将其右子树的左边孩子压栈
  33.         while (cur != null) {
  34.             stack.push(cur);
  35.             cur = cur.left;
  36.         }
  37.         // 返回当前结点值
  38.         return value;
  39.     }
  41.     public boolean hasNext() {
  42.         // 等价于，判断栈是否为空
  43.         return !stack.isEmpty();
  44.     }
  45. }
  47. /**
  48.  * Your BSTIterator object will be instantiated and called as such:
  49.  * BSTIterator obj = new BSTIterator(root);
  50.  * int param_1 = obj.next();
  51.  * boolean param_2 = obj.hasNext();
  52.  */