自从Hiring Freez结束后，各大厂都开始了疯狂涨薪内卷。
作为股票涨幅在FLAG中排名第一的谷歌，可以说的涨的非常低调：虽然base不变，但stock和bonus可没说不涨。
一道谷歌算法真题，带你了解一下面试难度👇
LintCode 86

二叉查找树迭代器

题目描述

设计实现一个带有下列属性的二叉查找树的迭代器：
next()返回BST中下一个最小的元素
  • 元素按照递增的顺序被访问（比如中序遍历）
  • next（）和hasNext（）的询问操作要求均摊时间复杂度是O(1)

扫码免费做题

↓↓↓
样例1
输入：
tree = {10,1,11,#,6,#,12}
输出：
[1,6,10,11,12]
解释：
二叉查找树如下 :10/\1 11\ \6 12可以返回二叉查找树的中序遍历[1,6,10,11,12]
样例2
输入：
tree = {2,1,3}
输出：
[1,2,3]
解释：
二叉查找树如下 :2/\1 3可以返回二叉查找树的中序遍历[1,2,3]

解题思路

这是一个非常通用的利用 stack 进行 Binary Tree Iterator 的写法。
stack 中保存一路走到当前节点的所有节点，stack.peek() 一直指向 iterator 指向的当前节点。因此判断有没有下一个，只需要判断 stack 是否为空 获得下一个值，只需要返回 stack.peek() 的值，并将 stack 进行相应的变化，挪到下一个点。
挪到下一个点的算法如下：
1、如果当前点存在右子树，那么就是右子树中“一路向西”最左边的那个点
2、如果当前点不存在右子树，则是走到当前点的路径中，第一个左拐的点
访问所有节点用时O(n)，所以均摊下来访问每个节点的时间复杂度时O(1)

源代码

publicclassBSTIterator {private Stack<TreeNode> stack = new Stack<>();// @param root: The root of binary tree.publicBSTIterator(TreeNode root){while (root != null) {stack.push(root); root = root.left; } }//@return: True if there has next node, or falsepublic boolean hasNext(){return !stack.isEmpty(); }//@return: return next nodepublic TreeNode next(){ TreeNode curt = stack.peek(); TreeNode node = curt;// move to the next nodeif (node.right == null) { node = stack.pop();while (!stack.isEmpty() && stack.peek().right == node) { node = stack.pop(); } } else { node = node.right;while (node != null) {stack.push(node); node = node.left; } }return curt; }}
继续阅读
阅读原文
关键词
右子树
元素
node.right
当前节点
stack.peek