|
| 1 | +```text |
| 2 | +题目: 实现一个二叉搜索树迭代器;你将使用二叉搜索树的根节点初始化迭代器 |
| 3 | + 调用next()将返回二叉搜索树中的下一个最小的数; |
| 4 | + 提示： |
| 5 | + next()和hasNext()操作的时间复杂度是O(1),并使用O(h)内存,其中h是树的高度; |
| 6 | + 你可以假设next()调用总是有效的,也就是说,当调用next()时,BST中至少存在一个下一个最小的数; |
| 7 | +1.栈+中序遍历: |
| 8 | + [1]思路: |
| 9 | + (1)在构造方法中通过中序遍历将结果放入双端队列中,由于是二叉搜索树,中序遍历得到的值是递增的; |
| 10 | + (2)获取下一个最小值: 只需要从双端队列中吐出头部值 |
| 11 | + (3)判断是否有下个最小值: 只需判断双端队列中是否还有值 |
| 12 | + [2]实现: |
| 13 | + class BSTIterator { |
| 14 | + private Deque<Integer> stack; |
| 15 | + public BSTIterator(TreeNode root) { |
| 16 | + stack = new ArrayDeque<>(); |
| 17 | + // 定义一个节点指向给定的遍历节点 |
| 18 | + TreeNode curr = root; |
| 19 | + Deque<TreeNode> nodeStack = new ArrayDeque<>(); |
| 20 | + // 结合栈实现二叉树的中序遍历 |
| 21 | + while (curr != null || !nodeStack.isEmpty()){ |
| 22 | + // 只要当前节点不为null则放到栈中,并向下个左子节点移动 |
| 23 | + while (curr !=null){ |
| 24 | + nodeStack.push(curr); |
| 25 | + curr = curr.left; |
| 26 | + } |
| 27 | + curr = nodeStack.pop(); |
| 28 | + stack.addLast(curr.val); |
| 29 | + curr = curr.right; |
| 30 | + } |
| 31 | + } |
| 32 | + /** @return the next smallest number */ |
| 33 | + public int next() { |
| 34 | + return stack.pollFirst(); |
| 35 | + } |
| 36 | + /** @return whether we have a next smallest number */ |
| 37 | + public boolean hasNext() { |
| 38 | + return !stack.isEmpty(); |
| 39 | + } |
| 40 | + } |
| 41 | + public class TreeNode { |
| 42 | + int val; |
| 43 | + TreeNode left; |
| 44 | + TreeNode right; |
| 45 | + TreeNode(int x) { val = x; } |
| 46 | + } |
| 47 | + [3]复杂度分析: |
| 48 | + (1)时间复杂度: O(N),N为树节点的个数,每个节点都需要遍历到一次 |
| 49 | + (2)空间复杂度: O(N),N为树节点的个数,双端队列需要存储所有树节点的值 |
| 50 | +2.递归+中序遍历: (自行实现) |
0 commit comments