问题描述
使用递归对二叉树进行后遍历的算法是什么?
What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?
推荐答案
这里的链接提供了另外两个解决方案，而无需使用任何已访问标志.
Here's a link which provides two other solutions without using any visited flags.
https://leetcode.com/problems/binary-tree-postorder-traversal/
由于树中缺少父指针，因此这显然是基于堆栈的解决方案. (如果有父指针，我们就不需要堆栈.)
This is obviously a stack-based solution due to the lack of parent pointer in the tree. (We wouldn't need a stack if there's parent pointer).
我们将首先将根节点推入堆栈.当堆栈不为空时，我们不断从堆栈顶部推入节点的左子节点.如果左孩子不存在，我们推它的右孩子.如果它是叶节点，我们将处理该节点并将其从堆栈中弹出.
We would push the root node to the stack first. While the stack is not empty, we keep pushing the left child of the node from top of stack. If the left child does not exist, we push its right child. If it's a leaf node, we process the node and pop it off the stack.
我们还使用变量来跟踪先前遍历的节点.目的是确定遍历是否是树的下降/上升，我们还可以知道它是否从左/右上升.
We also use a variable to keep track of a previously-traversed node. The purpose is to determine if the traversal is descending/ascending the tree, and we can also know if it ascend from the left/right.
如果我们从左侧升起树，我们不想再将其左侧的子级推入堆栈，并且如果右侧的子级存在，则应该继续沿树级下移.如果我们从右边将树升序，则应该对其进行处理并将其从堆栈中弹出.
If we ascend the tree from the left, we wouldn't want to push its left child again to the stack and should continue ascend down the tree if its right child exists. If we ascend the tree from the right, we should process it and pop it off the stack.
在以下3种情况下，我们将处理该节点并将其弹出堆栈:
We would process the node and pop it off the stack in these 3 cases:
- 该节点是叶节点(无子节点)
- 我们只是从左边穿过树而没有右边的孩子.
- 我们只是从右边穿过树.
这篇关于无需递归遍历二叉树的订单顺序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！