Morris遍历对于O（n）时间和O（1）空间的InOrder遍历非常有用。是否可以通过改变一些事情来实现PreOrder和PostOrder遍历使用相同的算法。
我知道使用morison Algo预订的解决方案。
这是java代码
public static void morisonPreOrder(TreeNode root) {
TreeNode curr = root, tmp=null;
while (curr != null) {
if(curr.leftNode == null) {
System.out.print(curr.value + " ");
curr = curr.rightNode;
} else {
tmp = curr.leftNode;
while (tmp.rightNode != null && tmp.rightNode != curr) {
tmp = tmp.rightNode;
}
if(tmp.rightNode == null) {
System.out.print(curr.value + " ");
tmp.rightNode = curr;
curr = curr.leftNode;
} else {
tmp.rightNode = null;
curr = curr.rightNode;
}
}
}
}
我不认为我们可以使用线程实现下单。在后期顺序中，我们必须遍历孩子然后他们的父母。我们可以建立从孩子到父母的链接，但在那之后我们不能上去这个父母因为他们没有链接。（一个指向左边的孩子，一个指向右边的孩子没有指向上方）
1
/ \
2 3
/ \
4 5
我们可以在指向节点5的4个右侧节点上创建一个线程。我们可以在指向节点2的5个右侧节点处创建一个线程。
但是在节点2处没有空指针来创建任何线程。节点2的指针已经指向节点4和5。
可以通过简单地反转有序Morris算法来实现后序。解释，
有序python Morris实现：
def in_order(root):
if not root:
return []
current = root
in_order_list = []
while current:
if not current.left:
in_order_list += [current.val] # Mark current as visited
current = current.right
else:
# find the right most of the left tree
predecessor = current.left
while (predecessor.right) and (predecessor.right != current):
predecessor = predecessor.right
# and create a link from this to current
if not predecessor.right:
predecessor.right = current
current = current.left
else: # now bring back the tree to it's original shape
predecessor.right = None
in_order_list += [current.val]
current = current.right
return in_order
对于后期订单，以current开头，如果current.right为空 - 开始向左看。如果没有，找到最左前的并将此前任的左侧链接回当前。 （简而言之，按顺序将左侧翻转为权限并继续将节点插入到访问列表的开头;））
下订单后的Python Morris
def post_order(root):
if not root:
return []
current = root
post_order_list = []
while current:
if not current.right:
post_order_list.insert(0, current.val)
current = current.left
else:
# find left most of the right sub-tree
predecessor = current.right
while (predecessor.left) and (predecessor.left != current):
predecessor = predecessor.left
# and create a link from this to current
if not predecessor.left:
post_order_list.insert(0, current.val)
predecessor.left = current
current = current.right
else:
predecessor.left = None
current = current.left
return post_order
以下是使用修改的morris遍历进行预订遍历的示例代码。
您可以使用类似的方式修改右前任的左侧链接以进行后期顺序遍历。
我没有时间测试代码。如果此代码出现问题，请告诉我。
void preOrderNonRecursive( BSTNode* root )
{
if(!root)
return;
BSTNode* cur = root;
while(cur)
{
bool b = false;
BSTNode* pre = NULL;
if (cur->left)
{
pre = cur->left;
while(pre->right && pre->right != cur)
pre = pre->right;
if(!pre->right)
{
pre->right = cur;
b = true;
}
else
pre->right = NULL;
}
else
printf("%d\n",cur->val);
if(b)
{
printf("%d\n",cur->val);
cur = cur->left;
}
else
cur = cur->right;
}
}
/ PreOrder实现没有堆栈和递归/
private static void morrisPreorder(){
while(node != null){
System.out.println(node.getData());
if (node.getLeftNode() == null){
node = node.getRightNode();
} else {
Node rightnode = node.getRightNode();
Node current = node.getLeftNode();
while(current.getRightNode() != null && current.getRightNode().getData() != node.getData())
current = current.getRightNode();
if(current.getRightNode() == null){
current.setRightNode(node.getRightNode());
node = node.getLeftNode();
} else {
node = node.getRightNode();
}
}
}
}
上面已经回答了前序遍历。
对于后序遍历，答案也是“是”。
您需要的唯一修改是：1。当前任的右子节点是当前节点时，将右子节点设置为null并反向输出当前节点的左子节点到前一节点的所有节点。 2.设置虚拟节点并将其左子节点设置为树的根节点。
Java代码写在这里：
private void printPostTraverse(List<Integer> traverseList, TreeNode start, TreeNode end) {
TreeNode node = start;
int insertIndex = traverseList.size();
while (node != end) {
traverseList.add(insertIndex, node.val);
node = node.right;
}
traverseList.add(insertIndex, node.val);
}
public List<Integer> postorderMorrisTraversal(TreeNode root) {
List<Integer> traverseList = new ArrayList<>();
TreeNode dummy = new TreeNode(-1);
dummy.left = root;
TreeNode cur = dummy, prev = null;
while (cur != null) {
if (cur.left == null) {
cur = cur.right;
} else {
prev = cur.left;
while (prev.right != null && prev.right != cur)
prev = prev.right;
if (prev.right == null) {
prev.right = cur;
cur = cur.left;
} else {
// Modification on get the traversal list
printPostTraverse(traverseList, cur.left, prev);
prev.right = null;
cur = cur.right;
}
}
}
return traverseList;
}