所以我熟悉后序遍历:为什么2堆栈对于后序横向如此有效
L - > R - > P(从左到右到父)。
我看到了可以执行相当漂亮使用2个叠一个序遍历代码:
public void postOrderTransverse(Node r){
if(r == null){return;}
Stack<Node> s = new Stack<Node>();
Stack<Node> reverser = new Stack<Node>();
s.push(r);
while(!s.isEmpty()){
Node temp = s.pop();
reverser.push(temp);
if (temp.left != null){
s.push(temp.left);}
if(temp.right != null){
s.push(temp.right);}
}
while(!reverser.empty()){
System.out.print(reverser.peek());
reverser.pop();
}
}
(通过http://articles.leetcode.com/binary-tree-post-order-traversal/)
,其中从本质上讲,一个堆栈只是反转等。我只是很好奇这是如何工作的。我有一个假设,Stack s接受输入,以便输出将类似于P - > R - > L,并且它只是将它传递到堆栈反转器,它将L - > R .-> P排出,因为它是后进先出。
但是,只是想通过这个算法的过程来思考,我很努力地理解Stack如何以及为什么以它的输入方式来处理它。希望我能在这里得到一些见解!谢谢:)
它使用第一组做一个前序遍历,结果推到第二组,然后弹出该栈,它给你仅仅通过反转结果来进行后序遍历。 – EJP
@EJP,它没有进行预定义遍历,因为它首先遍历右边的节点。事实上,这是一个递归的后序遍历的循环版本。 – user3707125