二阶树的发布顺序遍历而不递归
问题描述 投票：56回答：25
在不使用递归的情况下，对二叉树进行后序遍历的算法是什么？
25个回答
31
投票
投票
这是一个链接，提供了两个其他解决方案，而不使用任何访问过的标志。
https://leetcode.com/problems/binary-tree-postorder-traversal/
由于树中缺少父指针，这显然是基于堆栈的解决方案。 （如果有父指针，我们就不需要堆栈）。
我们首先将根节点推送到堆栈。当堆栈不为空时，我们继续从堆栈顶部推送节点的左子节点。如果左孩子不存在，我们会推动其正确的孩子。如果它是叶节点，我们处理节点并将其从堆栈中弹出。
我们还使用变量来跟踪先前遍历的节点。目的是确定遍历是否正在下降/上升树，我们也可以知道它是否从左/右上升。
如果我们从左边提升树，我们就不想再将它的左子移动到堆栈中，如果它的右子存在，它应该继续向下爬树。如果我们从右边提升树，我们应该处理它并将其从堆栈中弹出。
在这3种情况下，我们将处理节点并将其从堆栈中弹出：
- 节点是叶节点（没有子节点）
- 我们只是从左边遍历树，没有正确的孩子。
- 我们只是从右边遍历树。
0
投票
投票
在这里，我在c＃（。net）中粘贴不同版本以供参考:(对于有序迭代遍历，您可以参考：Help me understand Inorder Traversal without using recursion）
- 维基（http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations）（优雅）
- 单个堆栈的另一个版本（＃1和＃2：基本上使用这样的事实：在访问实际节点之前，访问顺序遍历正确的子节点 - 因此，我们只需要检查堆栈顶部的正确子节点是否确实是最后发布的订单遍历节点已被访问过 - 我在下面的代码片段中添加了评论以获取详细信息）
- 使用两个堆栈版本（参考：http://www.geeksforgeeks.org/iterative-postorder-traversal/）（更简单：基本上后期顺序遍历反向只是预订序遍历，通过简单的调整，首先访问右节点，然后是左节点）
- 使用访客标志（简单）
- 单元测试
~
public string PostOrderIterative_WikiVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = this._root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while ((stack.Count > 0)//stack is not empty
|| (iterativeNode != null))
{
if (iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
else
{
var stackTop = stack.Peek();
if((stackTop.Right != null)
&& (stackTop.Right != lastPostOrderTraversalNode))
{
//i.e. last traversal node is not right element, so right sub tree is not
//yet, traversed. so we need to start iterating over right tree
//(note left tree is by default traversed by above case)
iterativeNode = stackTop.Right;
}
else
{
//if either the iterative node is child node (right and left are null)
//or, stackTop's right element is nothing but the last traversal node
//(i.e; the element can be popped as the right sub tree have been traversed)
var top = stack.Pop();
Debug.Assert(top == stackTop);
nodes.Add(top.Element);
lastPostOrderTraversalNode = top;
}
}
}
}
return this.ListToString(nodes);
}
这是一个堆栈的邮件订单遍历（我的版本）
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if ((iterativeNode.Left == null)
&& (iterativeNode.Right == null))
{
nodes.Add(iterativeNode.Element);
lastPostOrderTraversalNode = iterativeNode;
//make sure the stack is not empty as we need to peek at the top
//for ex, a tree with just root node doesn't have to enter loop
//and also node Peek() will throw invalidoperationexception
//if it is performed if the stack is empty
//so, it handles both of them.
while(stack.Count > 0)
{
var stackTop = stack.Peek();
bool removeTop = false;
if ((stackTop.Right != null) &&
//i.e. last post order traversal node is nothing but right node of
//stacktop. so, all the elements in the right subtree have been visted
//So, we can pop the top element
(stackTop.Right == lastPostOrderTraversalNode))
{
//in other words, we can pop the top if whole right subtree is
//traversed. i.e. last traversal node should be the right node
//as the right node will be traverse once all the subtrees of
//right node has been traversed
removeTop = true;
}
else if(
//right subtree is null
(stackTop.Right == null)
&& (stackTop.Left != null)
//last traversal node is nothing but the root of left sub tree node
&& (stackTop.Left == lastPostOrderTraversalNode))
{
//in other words, we can pop the top of stack if right subtree is null,
//and whole left subtree has been traversed
removeTop = true;
}
else
{
break;
}
if(removeTop)
{
var top = stack.Pop();
Debug.Assert(stackTop == top);
lastPostOrderTraversalNode = top;
nodes.Add(top.Element);
}
}
}
else
{
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
使用两个堆栈
public string PostOrderIterative_TwoStacksVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
rightLeftPreOrderStack.Push(this._root);
while(rightLeftPreOrderStack.Count > 0)
{
var top = rightLeftPreOrderStack.Pop();
postOrderStack.Push(top);
if(top.Left != null)
{
rightLeftPreOrderStack.Push(top.Left);
}
if(top.Right != null)
{
rightLeftPreOrderStack.Push(top.Right);
}
}
while(postOrderStack.Count > 0)
{
var top = postOrderStack.Pop();
nodes.Add(top.Element);
}
}
return this.ListToString(nodes);
}
使用C＃（.net）中的访问标志：
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
//reset the flag, for further traversals
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
定义：
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public bool visted;
}
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
单元测试
[TestMethod]
public void PostOrderTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
string s1 = bst.PostOrderRecursive();
string s2 = bst.PostOrderIterativeWithVistedFlag();
string s3 = bst.PostOrderIterative();
string s4 = bst.PostOrderIterative_WikiVersion();
string s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
bst.Add(e);
bst.Delete(e);
bst.Add(e);
s1 = bst.PostOrderRecursive();
s2 = bst.PostOrderIterativeWithVistedFlag();
s3 = bst.PostOrderIterative();
s4 = bst.PostOrderIterative_WikiVersion();
s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
}
Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
}
0
投票
投票
Python有1个堆栈而没有标志：
def postorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if previous and ((previous is current) or (previous is current.left) or (previous is current.right)):
ret.append(current.val)
else:
stack.append(current)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return ret
更好的是使用类似的语句，顺序遍历也是如此
def inorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if None == previous or previous.left is current or previous.right is current:
if current.right:
stack.append(current.right)
stack.append(current)
if current.left:
stack.append(current.left)
else:
ret.append(current.val)
return ret
0
投票
投票
我没有添加节点类，因为它不是特别相关或任何测试用例，而是将它们作为阅读器等的练习。
void postOrderTraversal(node* root)
{
if(root == NULL)
return;
stack<node*> st;
st.push(root);
//store most recent 'visited' node
node* prev=root;
while(st.size() > 0)
{
node* top = st.top();
if((top->left == NULL && top->right == NULL))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
else
{
//we can check if we are going back up the tree if the current
//node has a left or right child that was previously outputted
if((top->left == prev) || (top->right== prev))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
if(top->right != NULL)
st.push(top->right);
if(top->left != NULL)
st.push(top->left);
}
}
cerr<<endl;
}
运行时间O（n） - 需要访问所有节点和空间O（n） - 对于堆栈，最坏情况树是单行链表
0
投票
投票
很高兴看到这么多激动人心的方法解决这个问题。非常鼓舞人心！
我遇到了这个主题，寻找一个简单的迭代解决方案，用于删除二叉树实现中的所有节点。我尝试了其中的一些，我尝试了网上其他地方发现的类似内容，但没有一个真的符合我的喜好。
问题是，我正在开发一个用于特定目的的数据库索引模块（比特币区块链索引），我的数据存储在磁盘上，而不是存储在RAM中。我根据需要交换页面，进行自己的内存管理。它速度较慢，但速度足够快，而且存储在磁盘而不是RAM上，我对浪费空间没有宗教信仰（硬盘很便宜）。
出于这个原因，我的二叉树中的节点有父指针。那是（所有）我正在谈论的额外空间。我需要父母，因为我需要为了各种目的迭代在树中上升和下降。
考虑到这一点，我很快写下了一小段关于如何完成的伪代码，即在运行时删除节点的后序遍历。它已经实施和测试，并成为我的解决方案的一部分。它也很快。
问题是：当节点有父指针时，它真的，真的很简单，而且因为我可以将父节点的链接归零到“刚刚离开”的节点。
这是迭代后序删除的伪代码：
Node current = root;
while (current)
{
if (current.left) current = current.left; // Dive down left
else if (current.right) current = current.right; // Dive down right
else
{
// Node "current" is a leaf, i.e. no left or right child
Node parent = current.parent; // assuming root.parent == null
if (parent)
{
// Null out the parent's link to the just departing node
if (parent.left == current) parent.left = null;
else parent.right = null;
}
delete current;
current = parent;
}
}
root = null;
如果您对编写复杂集合的更理论方法感兴趣（例如我的二叉树，它实际上是一个自平衡的红黑树），那么请查看以下链接：
http://opendatastructures.org/versions/edition-0.1e/ods-java/6_2_BinarySearchTree_Unbala.html http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
快乐的编码:-)
SørenFoghttp://iprotus.eu/
0
投票
投票
深度优先，后期订单，非递归，无堆栈
当你有父母时：
node_t
{
left,
right
parent
}
traverse(node_t rootNode)
{
bool backthreading = false
node_t node = rootNode
while(node <> 0)
if (node->left <> 0) and backthreading = false then
node = node->left
continue
endif
>>> process node here <<<
if node->right <> 0 then
lNode = node->right
backthreading = false
else
node = node->parent
backthreading = true
endif
endwhile
0
投票
投票
1.1创建一个空堆栈
2.1当root不为NULL时，请执行以下操作
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2从堆栈弹出一个项目并将其设置为root。
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3当堆栈不为空时，重复步骤2.1和2.2。
0
投票
投票
这是具有两个堆栈的Java实现
public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
if (root == null) {
return Collections.emptyList();
}
List<T> result = new ArrayList<T>();
Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
firstLevel.push(root);
while (!firstLevel.isEmpty()) {
BinaryTreeNode<T> node = firstLevel.pop();
secondLevel.push(node);
if (node.hasLeftChild()) {
firstLevel.push(node.getLeft());
}
if (node.hasRightChild()) {
firstLevel.push(node.getRight());
}
}
while (!secondLevel.isEmpty()) {
result.add(secondLevel.pop().getData());
}
return result;
}
这是单元测试
@Test
public void iterativePostOrderTest() {
BinaryTreeNode<Integer> bst = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});
assertThat(BinaryTreeUtil.iPostOrder(bst).toArray(new Integer[0]), equalTo(new Integer[]{4,5,2,6,7,3,1}));
}
0
投票
投票
/**
* This code will ensure holding of chain(links) of nodes from the root to till the level of the tree.
* The number of extra nodes in the memory (other than tree) is height of the tree.
* I haven't used java stack instead used this ParentChain.
* This parent chain is the link for any node from the top(root node) to till its immediate parent.
* This code will not require any altering of existing BinaryTree (NO flag/parent on all the nodes).
*
* while visiting the Node 11; ParentChain will be holding the nodes 9 -> 8 -> 7 -> 1 where (-> is parent)
*
* 1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 7
/ \ /
/ \ /
/ \ /
/ \ /
3 6 8
/ \ /
/ \ /
4 5 9
/ \
10 11
*
* @author ksugumar
*
*/
public class InOrderTraversalIterative {
public static void main(String[] args) {
BTNode<String> rt;
String[] dataArray = {"1","2","3","4",null,null,"5",null,null,"6",null,null,"7","8","9","10",null,null,"11",null,null,null,null};
rt = BTNode.buildBTWithPreOrder(dataArray, new Counter(0));
BTDisplay.printTreeNode(rt);
inOrderTravesal(rt);
}
public static void postOrderTravesal(BTNode<String> root) {
ParentChain rootChain = new ParentChain(root);
rootChain.Parent = new ParentChain(null);
while (root != null) {
//Going back to parent
if(rootChain.leftVisited && rootChain.rightVisited) {
System.out.println(root.data); //Visit the node.
ParentChain parentChain = rootChain.Parent;
rootChain.Parent = null; //Avoid the leak
rootChain = parentChain;
root = rootChain.root;
continue;
}
//Traverse Left
if(!rootChain.leftVisited) {
rootChain.leftVisited = true;
if (root.left != null) {
ParentChain local = new ParentChain(root.left); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.left;
continue;
}
}
//Traverse RIGHT
if(!rootChain.rightVisited) {
rootChain.rightVisited = true;
if (root.right != null) {
ParentChain local = new ParentChain(root.right); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.right;
continue;
}
}
}
}
class ParentChain {
BTNode<String> root;
ParentChain Parent;
boolean leftVisited = false;
boolean rightVisited = false;
public ParentChain(BTNode<String> node) {
this.root = node;
}
@Override
public String toString() {
return root.toString();
}
}
0
投票
投票
void display_without_recursion(struct btree **b)
{
deque< struct btree* > dtree;
if(*b)
dtree.push_back(*b);
while(!dtree.empty() )
{
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
if(t->right)
dtree.push_front(t->right);
if(t->left)
dtree.push_front(t->left);
}
cout << endl;
}
0
投票
投票
import java.util.Stack;
class Practice
{
public static void main(String arr[])
{
Practice prc = new Practice();
TreeNode node1 = (prc).new TreeNode(1);
TreeNode node2 = (prc).new TreeNode(2);
TreeNode node3 = (prc).new TreeNode(3);
TreeNode node4 = (prc).new TreeNode(4);
TreeNode node5 = (prc).new TreeNode(5);
TreeNode node6 = (prc).new TreeNode(6);
TreeNode node7 = (prc).new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
postOrderIteratively(node1);
}
public static void postOrderIteratively(TreeNode root)
{
Stack<Entry> stack = new Stack<Entry>();
Practice prc = new Practice();
stack.push((prc).new Entry(root, false));
while (!stack.isEmpty())
{
Entry entry = stack.pop();
TreeNode node = entry.node;
if (entry.flag == false)
{
if (node.right == null && node.left == null)
{
System.out.println(node.data);
} else
{
stack.push((prc).new Entry(node, true));
if (node.right != null)
{
stack.push((prc).new Entry(node.right, false));
}
if (node.left != null)
{
stack.push((prc).new Entry(node.left, false));
}
}
} else
{
System.out.println(node.data);
}
}
}
class TreeNode
{
int data;
int leafCount;
TreeNode left;
TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public int getLeafCount()
{
return leafCount;
}
public void setLeafCount(int leafCount)
{
this.leafCount = leafCount;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
@Override
public String toString()
{
return "" + this.data;
}
}
class Entry
{
Entry(TreeNode node, boolean flag)
{
this.node = node;
this.flag = flag;
}
TreeNode node;
boolean flag;
@Override
public String toString()
{
return node.toString();
}
}
}
34
投票
投票
这是具有一个堆栈且没有访问标志的版本：
private void postorder(Node head) {
if (head == null) {
return;
}
LinkedList<Node> stack = new LinkedList<Node>();
stack.push(head);
while (!stack.isEmpty()) {
Node next = stack.peek();
boolean finishedSubtrees = (next.right == head || next.left == head);
boolean isLeaf = (next.left == null && next.right == null);
if (finishedSubtrees || isLeaf) {
stack.pop();
System.out.println(next.value);
head = next;
}
else {
if (next.right != null) {
stack.push(next.right);
}
if (next.left != null) {
stack.push(next.left);
}
}
}
}
0
投票
投票
我一直在寻找一个表现良好且易于定制的代码片段。螺纹树不是“简单”。双栈解决方案需要O（n）内存。 tcb的LeetCode解决方案和解决方案有额外的检查和推动......
这是一个翻译成C的经典算法，对我有用：
void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
TreeNode *stack[40]; // simple C stack, no overflow check
TreeNode **sp = stack;
TreeNode *last_visited = NULL;
for (; p != NULL; p = p->left)
*sp++ = p;
while (sp != stack) {
p = sp[-1];
if (p->right == NULL || p->right == last_visited) {
visit(p);
last_visited = p;
sp--;
} else {
for (p = p->right; p != NULL; p = p->left)
*sp++ = p;
}
}
}
恕我直言这个算法比表现良好和可读的wikipedia.org / Tree_traversal伪代码更容易理解。有关光荣的细节，请参阅Knuth第1卷中关于二叉树练习的答案。
0
投票
投票
这是一个Python版本::
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def postOrderIterative(root):
if root is None :
return
s1 = []
s2 = []
s1.append(root)
while(len(s1)>0):
node = s1.pop()
s2.append(node)
if(node.left!=None):
s1.append(node.left)
if(node.right!=None):
s1.append(node.right)
while(len(s2)>0):
node = s2.pop()
print(node.data)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)
这是输出::
0
投票
投票
因此，您可以使用一个堆栈进行后期订单遍历。
private void PostOrderTraversal(Node pos) {
Stack<Node> stack = new Stack<Node>();
do {
if (pos==null && (pos=stack.peek().right)==null) {
for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
} else if(pos!=null) {
stack.push(pos);
pos=pos.left;
}
} while (!stack.isEmpty());
}
0
投票
投票
Post Order遍历的逻辑，不使用Recursion
在Postorder traversal，处理顺序是left-right-current。因此，在访问其他部分之前，我们需要先访问左侧部分。我们将尝试为树的每个节点尽可能地向下遍历树。对于每个当前节点，如果存在正确的子节点，则在推送当前节点之前将其推入堆栈，而root不是NULL / None。现在从堆栈中弹出一个节点，检查该节点的右子节点是否存在。如果存在，则检查它是否与顶部元素相同。如果它们相同则表明我们还没有使用正确的部分，所以在处理当前节点之前，我们必须处理正确的部分，并且为了弹出顶部元素（右子节点）并将当前节点推回到堆栈中。每次我们的头都是弹出的元素。如果当前元素与top不同并且head不是NULL，那么我们将完成左侧和右侧部分，因此现在我们可以处理当前节点。我们必须重复前面的步骤，直到堆栈为空。
def Postorder_iterative(head):
if head is None:
return None
sta=stack()
while True:
while head is not None:
if head.r:
sta.push(head.r)
sta.push(head)
head=head.l
if sta.top is -1:
break
head = sta.pop()
if head.r is not None and sta.top is not -1 and head.r is sta.A[sta.top]:
x=sta.pop()
sta.push(head)
head=x
else:
print(head.val,end = ' ')
head=None
print()
0
投票
投票
在没有递归的情况下执行Post Order Traversal的两种方法： 1.使用一个HashSet访问节点和一个堆栈进行回溯：
private void postOrderWithoutRecursion(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
visited.add(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null || visited.contains(root.right)) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
root = root.right;
}
}
}
}
时间复杂度：O（n） 空间复杂度：O（2n） 2.使用树变更方法：
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
TreeNode temp = root.right;
root.right = null;
root = temp;
}
}
}
}
时间复杂度：O（n） 空间复杂度：O（n）
TreeNode类：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
0
投票
投票
这是一个简短的（walker是3行）版本，我需要用Python编写一般树。当然，也适用于更有限的二叉树。树是节点和子列表的元组。它只有一个堆栈。显示的示例用法。
def postorder(tree):
def do_something(x): # Your function here
print(x),
def walk_helper(root_node, calls_to_perform):
calls_to_perform.append(partial(do_something, root_node[0]))
for child in root_node[1]:
calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
calls_to_perform = []
calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
while calls_to_perform:
calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))
d c b a
0
投票
投票
最简单的解决方案，它可能看起来不是最好的答案，但它很容易理解。我相信如果您已经理解了解决方案，那么您可以对其进行修改以获得最佳解决方案
//使用两个堆栈
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> st=new Stack<>();
Stack<TreeNode> st2=new Stack<>();
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)
return al;
st.push(root); //push the root to 1st stack
while(!st.isEmpty())
{
TreeNode curr=st.pop();
st2.push(curr);
if(curr.left!=null)
st.push(curr.left);
if(curr.right!=null)
st.push(curr.right);
}
while(!st2.isEmpty())
al.add(st2.pop().val);
//this ArrayList contains the postorder traversal
return al;
}
27
投票
投票
以下是来自wikipedia的样本：
nonRecursivePostorder(rootNode)
nodeStack.push(rootNode)
while (! nodeStack.empty())
currNode = nodeStack.peek()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push(currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push(currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop()
4
投票
投票
这是我用于迭代，后序遍历的方法。我喜欢这种方法，因为：
- 它只处理每个循环周期的单个转换，因此很容易遵循。
- 类似的解决方案适用于有序和预订遍历
码：
enum State {LEFT, RIGHT, UP, CURR}
public void iterativePostOrder(Node root) {
Deque<Node> parents = new ArrayDeque<>();
Node curr = root;
State state = State.LEFT;
while(!(curr == root && state == State.UP)) {
switch(state) {
case LEFT:
if(curr.left != null) {
parents.push(curr);
curr = curr.left;
} else {
state = RIGHT;
}
break;
case RIGHT:
if(curr.right != null) {
parents.push(curr);
curr = curr.right;
state = LEFT;
} else {
state = CURR;
}
break;
case CURR:
System.out.println(curr);
state = UP;
break;
case UP:
Node child = curr;
curr = parents.pop();
state = child == curr.left ? RIGHT : CURR;
break;
default:
throw new IllegalStateException();
}
}
}
说明：
你可以考虑这样的步骤：
- 尝试左 如果左节点存在：再次尝试LEFT 如果左节点不存在：请尝试右键
- 试试吧 如果存在右节点：从那里尝试LEFT 如果没有权利，那么你就是一片叶子：尝试CURR
- 试试CURR 打印当前节点 下面的所有节点都已执行（下订单）：尝试UP
- 试试吧 如果node是root，则没有UP，所以EXIT 如果从左边出来，请尝试右键 如果从右边开始，请尝试CURR
2
投票
投票
import java.util.Stack;
public class IterativePostOrderTraversal extends BinaryTree {
public static void iterativePostOrderTraversal(Node root){
Node cur = root;
Node pre = root;
Stack<Node> s = new Stack<Node>();
if(root!=null)
s.push(root);
System.out.println("sysout"+s.isEmpty());
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=null){
s.push(cur.left);
}
else if(cur.right!=null){
s.push(cur.right);
}
if(cur.left==null && cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=null){
s.push(cur.right);
}else if(cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.right){// we are traversing up the tree from the right
System.out.println(s.pop().data);
}
pre=cur;
}
}
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
Node root = bt.generateTree();
iterativePostOrderTraversal(root);
}
}
2
投票
投票
这是一个C ++解决方案，它不需要任何存储来保存树中的书籍。 相反，它使用两个堆栈。一个用于帮助我们遍历另一个用于存储节点，因此我们可以对它们进行遍历遍历。
std::stack<Node*> leftStack;
std::stack<Node*> rightStack;
Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
if( currentNode )
{
leftStack.push( currentNode );
currentNode = currentNode->m_left;
}
else
{
currentNode = leftStack.top();
leftStack.pop();
rightStack.push( currentNode );
currentNode = currentNode->m_right;
}
}
while( !rightStack.empty() )
{
currentNode = rightStack.top();
rightStack.pop();
std::cout << currentNode->m_value;
std::cout << "\n";
}
2
投票
投票
//带有标志的java版本
public static <T> void printWithFlag(TreeNode<T> root){
if(null == root) return;
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.add(root);
while(stack.size() > 0){
if(stack.peek().isVisit()){
System.out.print(stack.pop().getValue() + " ");
}else{
TreeNode<T> tempNode = stack.peek();
if(tempNode.getRight()!=null){
stack.add(tempNode.getRight());
}
if(tempNode.getLeft() != null){
stack.add(tempNode.getLeft());
}
tempNode.setVisit(true);
}
}
}
0
投票
投票
void postorder_stack(Node * root){
stack ms;
ms.top = -1;
if(root == NULL) return ;
Node * temp ;
push(&ms,root);
Node * prev = NULL;
while(!is_empty(ms)){
temp = peek(ms);
/* case 1. We are nmoving down the tree. */
if(prev == NULL || prev->left == temp || prev->right == temp){
if(temp->left)
push(&ms,temp->left);
else if(temp->right)
push(&ms,temp->right);
else {
/* If node is leaf node */
printf("%d ", temp->value);
pop(&ms);
}
}
/* case 2. We are moving up the tree from left child */
if(temp->left == prev){
if(temp->right)
push(&ms,temp->right);
else
printf("%d ", temp->value);
}
/* case 3. We are moving up the tree from right child */
if(temp->right == prev){
printf("%d ", temp->value);
pop(&ms);
}
prev = temp;
}
}
0
投票
投票
请参阅这个完整的Java实现。只需复制代码并粘贴到编译器中即可。它会工作正常。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Node
{
Node left;
String data;
Node right;
Node(Node left, String data, Node right)
{
this.left = left;
this.right = right;
this.data = data;
}
public String getData()
{
return data;
}
}
class Tree
{
Node node;
//insert
public void insert(String data)
{
if(node == null)
node = new Node(null,data,null);
else
{
Queue<Node> q = new LinkedList<Node>();
q.add(node);
while(q.peek() != null)
{
Node temp = q.remove();
if(temp.left == null)
{
temp.left = new Node(null,data,null);
break;
}
else
{
q.add(temp.left);
}
if(temp.right == null)
{
temp.right = new Node(null,data,null);
break;
}
else
{
q.add(temp.right);
}
}
}
}
public void postorder(Node node)
{
if(node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.print(node.getData()+" --> ");
}
public void iterative(Node node)
{
Stack<Node> s = new Stack<Node>();
while(true)
{
while(node != null)
{
s.push(node);
node = node.left;
}
if(s.peek().right == null)
{
node = s.pop();
System.out.print(node.getData()+" --> ");
if(node == s.peek().right)
{
System.out.print(s.peek().getData()+" --> ");
s.pop();
}
}
if(s.isEmpty())
break;
if(s.peek() != null)
{
node = s.peek().right;
}
else
{
node = null;
}
}
}
}
class Main
{
public static void main(String[] args)
{
Tree t = new Tree();
t.insert("A");
t.insert("B");
t.insert("C");
t.insert("D");
t.insert("E");
t.postorder(t.node);
System.out.println();
t.iterative(t.node);
System.out.println();
}
}
最新问题
- 包含比您需要的更多的头文件有什么缺点吗？
- 即使词序发生变化，我如何能够一致地将一个单词映射到句子中的另一个单词，例如将症状映射到受影响的器官？
- 如何处理 Symfony/PHP 中错误的 CSV 文件导入
- WPF 中的双向绑定 - 缓存对象位于另一个绑定对象内
- 在 SwiftUI 视图上叠加颜色？
- 搜索目标文件以查找保存在 .txt 或 .csv 中的术语并重新查找？
- 为什么我无法使用 Windows API 函数获得正确的光标坐标？
- AWS EC2 不断退出 Docker 容器（Jenkins 管道）
- 为什么 phpword 忽略 html 列表中的段落样式？
- 安装 webhook telegram bot 时如何设置 max_connections？
- 如何在 Java Spring 上等待订阅者完成 TEXT_EVENT_STREAM
- 无法在 VS CODE 中输入
- FFmpeg 错误：无法在过滤器 Parsed_amix_54 上找到未标记的输入板 0 的匹配流
- React/NextJS：如何映射键发生变化的对象数组？
- Javascript：Array(3).map() 与 [...Array(3)].map() 行为毫无意义
- 在详细区域内显示表格数据
- 将星期本地化为 DayOfWeek 枚举
- AstroJS+Svelte SSR 应用程序中的重定向不起作用
- 如何将Python请求的unicode输出转换为字典
- 利用 Google Colab w/Google Cloud w/python 生成图片，当我尝试使用种子时收到错误
© www.soinside.com 2019 - 2024. All rights reserved.