面试时 关于 "树" 肯定离不开三种遍历算法
前序遍历、后序遍历、中序遍历。通常面试要求不高的情况下、我们用递归方法实现就可以了、因为递归实现简单明了。但是有时候面试官也希望我们写出迭代版本的中序遍历、中序遍历在二叉查找树中、因为迭代结果是一个有序数组。
一般题目是希望我们实现 next 方法和 hashNext 方法、从而实现二叉查找树的中序遍历迭代器。
实现要点：
递归-> 非递归，意味着自己需要控制原来由操作系统控制的栈的进进出出。
如何找到最小的第一个点？
找到树的最左边的节点就可以了。
如何求出一个二叉树节点在中序遍历中的下一个节点？
在 stack 中记录从根节点到当前节点的整条路径
下一个节点
如果有右子树、那么下一个节点必然是右子树的最小点。
如果右子树为空，那么必定是上一个通过左子树包含当前的点。
话不多说、直接上代码
Stack<TreeNode> stack = new Stack<>();
public BstIterator(TreeNode root) { while (root != null) { stack.push(root); root = root.left; }}
public boolean hasNext() { return !stack.isEmpty();}
public TreeNode next() { TreeNode curt = stack.peek();//返回栈顶的元素。 TreeNode node = curt;
if (node.right == null) { //右子树为空的情况下、那么证明当前节点的下一个节点必然是通过左边路径遍历到当前节点的最近的那一个节点。 //如果stack的peek节点的右子树是node节点、证明stack的peek节点已经访问过了。直接pop就行、因为中序遍历 //先中间节点后右边节点。 node = stack.pop(); while (!stack.isEmpty() && stack.peek().right == node) { node = stack.pop(); } } else { //右子树不为空、那么将node的整个右子树的左子树加入到stack当中去 node = node.right; while (node != null) { stack.push(node); node = node.left; } } return curt;}
复制代码
我们以一个例子来模拟这个流程 主要观察 stack 中的值的变化
评论