我们可以使用 Morris 遍历进行后序吗？

Question

我访问了很多网站，但找不到任何用于 Morris postOrder 遍历的算法。我知道我们可以对 preOrder 使用 Morris 算法，如果有人向我指出 postOrder Morris 算法（如果存在），inOrder.It 将会有很大帮助。

Answer 1

我将尝试解释一下，我们如何使用 Morris 方法实现 post-order 遍历。 Pre-requirement : 在解释post-order遍历之前，我们先修改一下in-order遍历。

在In-order遍历中，从根节点开始 1. 如果当前节点已经离开 child 然后找到它的 in-order 前任并使根作为它的右 child 并移动到根的左侧。 [要找到前驱，找到其左子树中的最大元素] 2. 如果当前节点没有左 child ，则打印数据并向右移动。

恢复树：应该注意的主要事情是，在执行步骤 1 时，我们将到达一个点，其中前任右 child 本身就是当前节点，这只会发生在整个左 child 关闭，我们从那里开始打印数据。 [当你发现当前节点没有左边child时] 因此，对于这种情况，我们需要从该节点右切 child。

void MorriesInorder(BTnode root) {
if(root == null ) return; 
BTnode temp;
while ( root!=null){
   //case 2: when left child does not exist
      if ( root.left == null ) { 
               print( root.data );
               root = root.right;
    }else {
            //find predecessor 
             temp = root.left; 
             while ( temp.right!=null && 
                      temp.right!=root) //  to check restore case
                   temp = temp.right;

             if ( temp.right == null ) //predecessor found, converting
            { 
                      temp.right = root; 
                      root = root.left; 
            } else {
                  print root.data;
                  temp.right = null; //  cut right child off
                  root = root.right; 
             }
    }

}}

所以现在回到最初的问题，我们如何执行后序遍历。我们将使用上面的概念稍作修改来实现后序遍历。首先让我们有一个虚拟节点并将整个树作为虚拟节点的左 child 并使右 child 为空。 [ 为什么？因为如果我们假设没有 root 的右 child 然后 printng left child 然后 root 成为后序遍历，右 ;) ] 接下来呢？我们完成了吗，不... 只对新树执行排序没有任何意义，它仍然打印原始树的排序遍历，然后是虚拟节点。

首先从案例 2 中删除打印数据[在顺序遍历中讨论]

关键部分：现在仔细观察里面的else块，这是需要注意的代码段。由于这棵临时扩展的树是in-order遍历的主题除了在内部else子句中，在找到临时parent之后，p.left（包括）和p（排除）之间的节点) 在修改后的树中向右扩展以相反的顺序进行处理。为了在恒定时间内处理它们，向下扫描节点链并将右引用反转为引用 parent 个节点。然后向上扫描同一条链，访问每个节点，将正确的引用恢复到原来的设置。

//This is Post Order :children before node( L ,R , N)
void morrisPostorderTraversal(Node *root){

// Making our tree left subtree of a dummy Node
Node *dummyRoot = new Node(0);
dummyRoot->left = root;

//Think of P as the current node 
Node *p = dummyRoot, *pred, *first, *middle, *last;
while(p!=NULL){        

    if(p->left == NULL){
        p = p->right;
    } else{
        /* p has a left child => it also has a predeccessor
           make p as right child predeccessor of p    
        */
        pred = p->left;
        while(pred->right!=NULL && pred->right != p){
            pred = pred->right;
        }

        if(pred->right == NULL){ 

            // predeccessor found for first time
            // modify the tree

            pred->right = p;    
            p = p->left;

        }else {                          

           // predeccessor found second time
           // reverse the right references in chain from pred to p
            first = p;
            middle = p->left;              
            while(middle!=p){            
                last = middle->right;
                middle->right = first;
                first = middle;
                middle = last;
            }

            // visit the nodes from pred to p
            // again reverse the right references from pred to p    
            first = p;
            middle = pred;
            while(middle!=p){

                cout<<" "<<middle->data;  
                last = middle->right;          
                middle->right = first;
                first = middle;
                middle = last;
            }

            // remove the pred to node reference to restore the tree structure
            pred->right = NULL;    
            p = p-> right;
        }
    }
}    
}

Answer 2

我的 Java 解决方案 - 它有很多代码注释，但如果您需要更多解释，请在这里评论我。

public static void postOrder(Node root) {
    // ensures all descendants of root that are right-children
    //  (arrived at only by "recurring to right") get inner-threaded
    final Node fakeNode = new Node(0);    // prefer not to give data, but construction requires it as primitive
    fakeNode.left = root;

    Node curOuter = fakeNode;
    while(curOuter != null){    // in addition to termination condition, also prevents fakeNode printing
        if(curOuter.left != null){
            final Node curOuterLeft = curOuter.left;

            // Find in-order predecessor of curOuter
            Node curOuterInOrderPred = curOuterLeft;
            while(curOuterInOrderPred.right != null && curOuterInOrderPred.right != curOuter){
                curOuterInOrderPred = curOuterInOrderPred.right;
            }

            if(curOuterInOrderPred.right == null){
                // [Outer-] Thread curOuterInOrderPred to curOuter
                curOuterInOrderPred.right = curOuter;

                // "Recur" on left
                curOuter = curOuterLeft;

            } else {    // curOuterInOrderPred already [outer-] threaded to curOuter
                        //  -> [coincidentally] therefore curOuterLeft's left subtree is done processing
                // Prep for [inner] threading (which hasn't ever been done yet here)...
                Node curInner = curOuterLeft;
                Node curInnerNext = curInner.right;
                // [Inner-] Thread curOuterLeft [immediately backwards] to curOuter [its parent]
                curOuterLeft.right = curOuter;
                // [Inner-] Thread the same [immediately backwards] for all curLeft descendants
                //  that are right-children (arrived at only by "recurring" to right)
                while(curInnerNext != curOuter){
                    // Advance [inner] Node refs down 1 level (to the right)
                    final Node backThreadPrev = curInner;
                    curInner = curInnerNext;
                    curInnerNext = curInnerNext.right;
                    // Thread immediately backwards
                    curInner.right = backThreadPrev;
                }

                // curInner, and all of its ancestors up to curOuterLeft,
                //  are now indeed back-threaded to each's parent
                // Print them in that order until curOuter
                while(curInner != curOuter){
                    /*
                        -> VISIT
                     */
                    System.out.print(curInner.data + " ");

                    // Move up one level
                    curInner = curInner.right;
                }

                // "Recur" on right
                curOuter = curOuter.right;
            }

        } else {
            // "Recur" on right
            curOuter = curOuter.right;
        }
    }
}

class Node {
  Node left;
  Node right;
  int data;

  Node(int data) {
      this.data = data;
      left = null;
      right = null;
  }
}

Answer 3

一种更简单的方法是执行与预序莫里斯遍历对称相反的操作，并以相反的顺序打印节点。

    TreeNode* node = root;
    stack<int> s;
    while(node) {
        if(!node->right) {
            s.push(node->val);
            node = node->left;
        }
        else {
            TreeNode* prev = node->right;

            while(prev->left && prev->left != node)
                prev = prev->left;

            if(!prev->left) {
                prev->left = node;
                s.push(node->val);
                node = node->right;
            }
            else {  
                node = node->left;
                prev->left = NULL;
            }
        }
    }

    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    cout << endl;

Answer 4

一旦你理解了它背后的概念，它似乎很简单。

基本上，我们使用 In-order 遍历 (L-N-R) 打印给定二叉树的 post-order 遍历 (L-R-N)。我们需要做的就是反转中序遍历的第二部分和第三部分，即以 L-R-N.

的方式打印出来

当在线程创建阶段借助我们之前创建的线程再次访问一个节点时，这意味着我们完成了对左子树的遍历。因此我们需要打印所有左子树节点。所以，我们打印当前节点的左子节点和右子树的左子节点 child.

在这一步之后，我们已经打印了所有的左节点，现在我们需要做的就是逆序打印右指针。如果我们将其视为一个简单的单链表，其中下一个指针是右子树中每个节点的右child。

以相反的顺序打印列表直到当前节点。转到您保存的 In-order 后继节点并按照相同的顺序进行操作。

我希望它能让你更清楚一些。

PS：链表反转用于反转中序遍历的第二部分和第三部分。

Answer 5

莫里斯遍历 T(n) = O(n) S(n) = O(1)

视频 link - https://www.youtube.com/watch?v=80Zug6D1_r4

问题 link - https://leetcode.com/problems/binary-tree-postorder-traversal/

我们将先序Morris遍历从root->left->right修改为root->right->left。为此，我们需要再做一项更改。在正常的前序和中序中，我们从左子树的最右节点到当前节点创建线程，这里我们将从右子树的最左节点到当前节点创建线程，因为这里我们必须在左子树之前覆盖右子树

        class Solution {
        public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ans;
            while(root)
            {
                TreeNode *curr = root;//We will create thread from left most node of right subtree to present node and will travell to that node using curr
                                        
                if(curr->right)//if root has right child
                            //We can't push directly this root node val to ans as we are not sure whether we are here
                            //thorough thread link after covering right subtree or we are here for the first time
                {
                    curr = curr->right;
                    while(curr->left && curr->left != root)//go to left most node of right subtree
                        curr=curr->left;
                    if(curr->left != root)//not threaded yet
                    {
                        ans.push_back(root->val);//it means root was visited for first time and this is modified preorder hence 
                                                //push this node's val to ans
                        curr->left = root;//create the thread
                        root = root->right;//go to right to cover right subtree as modified preorder is root->right->left
                    }
                    else//was threaded
                    {
                        curr->left = NULL;//break the thread
                        root = root->left;//right subtree has been covered hence now cover the left one
                                            //no need to push this node value as we are here for the second time using thread
                                            //link
                    }
                }
                else//root hasn't right child
                {
                    ans.push_back(root->val);//modified preorder is root->right->left hence push this value before going to left
                    root = root->left;
                }
            }
            reverse(ans.begin(),ans.end());//reversing root->right->left to left->right->root to make it post order
            return ans;
        }
    };

我们可以使用 Morris 遍历进行后序吗？

Can we use Morris traversal for postorder?

algorithm

binary-tree

tree-traversal