通过修改morris遍历实现PreOrder和PostOrder遍历

Question

morris 遍历非常适合 O(n) 时间和 O(1) 空间的 InOrder 遍历。是否有可能仅通过改变一些东西就可以使用相同的算法实现 PreOrder 和 PostOrder 遍历。

Answer 1

我认为我们不能使用线程实现后序。
按照后序，我们必须遍历两个孩子，然后遍历他们的父母。
我们可以建立从子节点到父节点的链接，但之后我们无法向上移动这个父节点，因为它们没有链接。（一个指向左子节点，一个指向其右子节点，没有一个向上指向）

             1
            / \
           2   3
          / \
         4   5

我们可以在 4 的右节点创建一个线程指向节点 5 。
我们可以在 5 的右侧节点创建一个指向节点 2 的线程。

但在节点 2 处，没有空指针来创建任何线程。节点 2 已经有指向节点 4 和节点 4 的指针。 5.

Answer 2

我知道使用 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;
            }
        }
    }
}

Answer 3

后序可以通过简单地反转中序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

Answer 4

以下是使用修改后的莫里斯遍历进行前序遍历的示例代码。

可以用类似的方式修改右前驱的左链接进行后序遍历。

我没有时间测试代码。如果这段代码有问题，请告诉我。

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;
    }
}

Answer 5

/没有堆栈和递归的 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();
                }
            }
        }
    }

Answer 6

前序遍历上面已经回答了。

对于后序遍历，答案也是“是”。

您需要的唯一修改是：
1、当前驱的右子节点为当前节点时，将右子节点置为空，反向输出当前节点左子节点到前驱的所有节点。
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;
    }