一定要早日上岸鸭 · July 25, 2021 0

173. 二叉搜索树迭代器

173. 二叉搜索树迭代器

两种做法:

  1. 中序递归遍历:我们可以直接对二叉搜索树做一次完全的递归遍历,获取中序遍历的全部结果并保存在数组中。随后,我们利用得到的数组本身来实现迭代器。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class BSTIterator { private int idx; private List<Integer> ls; public BSTIterator(TreeNode root) { idx = 0; ls = new ArrayList<Integer>(); Inordertraversal(root, ls); } public int next() { int ret = ls.get(idx++); return ret; } public boolean hasNext() { if(idx>=ls.size() || ls.get(idx)==null) return false; else return true; } public void Inordertraversal(TreeNode root, List<Integer> ls){ if(root==null) return; Inordertraversal(root.left, ls); ls.add(root.val); Inordertraversal(root.right,ls); } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */

2. 运用栈来实现:先把所有左子树节点压入栈然后按顺序出栈:

  1. 先将当前节点的所有左子树压入栈,压到没有为止
  2. 将最后一个压入的节点弹出(栈顶元素),加入答案
  3. 将当前弹出的节点作为当前节点,重复步骤一
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class BSTIterator { Deque<TreeNode> stack; public BSTIterator(TreeNode root) { stack = new ArrayDeque<>(); inStack(root); } public int next() { TreeNode temp = stack.pollLast(); int res = temp.val; temp = temp.right; inStack(temp); return res; } public void inStack(TreeNode root){ while(root!=null){ stack.addLast(root); root = root.left; } } public boolean hasNext() { return !stack.isEmpty(); } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */