Morris transversal para Postorder

Realice el recorrido del árbol de orden posterior utilizando Morris Traversal .

Ejemplos:

Entrada:         1
             / \
           2 3
        / \ / \
       6 7 8 9

Salida: 6 7 2 8 9 3 1

Entrada:         5
             / \
           2 3
        / \ / \
       4 N 8 9

Salida: 4 2 8 9 3 5

Enfoque: el enfoque para realizar Morris Traversal para Postorder es similar al Morris Traversal para Preorder, excepto que se intercambia entre los enlaces de Node izquierdo y derecho.

• Crear un vector e inicializar actual como raíz
• Mientras que la corriente no es NULL
  • Si el actual no tiene un hijo derecho
    • presione la tecla actual en el vector
          Ir a la izquierda, es decir, actual = actual->izquierda
  • más
    • Encuentre el Node más a la izquierda en el subárbol derecho actual O el Node cuyo hijo izquierdo == actual.
  • si actual no tiene un hijo izquierdo
    • presione la tecla actual en el vector
    • Hacer actual a partir del hijo izquierdo de ese Node más a la izquierda
    • Ir a este hijo derecho, es decir, actual = actual->derecho
  • más
    • Encontrado hijo izquierdo == actual
  • Actualice el hijo izquierdo como NULL de ese Node cuyo hijo izquierdo es actual
  • Ir a la izquierda, es decir actual = actual->izquierda  
     
• En el último, invertimos el vector y lo imprimimos, dado que el vector se usa para almacenar la salida, la complejidad espacial de este algoritmo sería O(N).

A continuación se muestra la implementación del enfoque anterior.

// C++ program to perform
// Morris Traversal for Postorder
#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(int data)
    {
        key = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function to print vector
void print(vector<int>& ans)
{
    // Print the vector elements
    for (auto x : ans) {
        cout << x << " ";
    }
}
 
// Postorder traversal
// Without recursion and without stack
vector<int> postorderTraversal(TreeNode* root)
{
    vector<int> res;
    TreeNode* current = root;
 
    while (current != NULL) {
        // If right child is null,
        // put the current node data
        // in res. Move to left child.
        if (current->right == NULL) {
            res.push_back(current->key);
            current = current->left;
        }
        else {
            TreeNode* predecessor = current->right;
            while (predecessor->left != NULL
                   && predecessor->left != current) {
                predecessor = predecessor->left;
            }
            // If left child doesn't point
            // to this node, then put in res
            // this node and make left
            // child point to this node
            if (predecessor->left == NULL) {
                res.push_back(current->key);
                predecessor->left = current;
                current = current->right;
            }
            // If the left child of inorder predecessor
            // already points to this node
            else {
                predecessor->left = NULL;
                current = current->left;
            }
        }
    }
    // reverse the res
    reverse(res.begin(), res.end());
    return res;
}
// Driver program
int main()
{
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->right->left = new TreeNode(40);
    root->right->right = new TreeNode(50);
   
    cout << "Morris(postorder) Traversal: ";
    vector<int> ans = postorderTraversal(root);
   
    print(ans);
    return 0;
}

// Java program to perform
// Morris Traversal for Postorder
import java.util.*;
class GFG{
 
static class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;
 
    TreeNode(int data)
    {
        key = data;
        left = null;
        right = null;
    }
};
 
// Function to print vector
static void print(Vector<Integer> ans)
{
    // Print the vector elements
    for (int x : ans) {
        System.out.print(x+ " ");
    }
}
 
// Postorder traversal
// Without recursion and without stack
static Vector<Integer> postorderTraversal(TreeNode root)
{
    Vector<Integer> res = new Vector<>();
    TreeNode current = root;
 
    while (current != null)
    {
       
        // If right child is null,
        // put the current node data
        // in res. Move to left child.
        if (current.right == null) {
            res.add(current.key);
            current = current.left;
        }
        else {
            TreeNode predecessor = current.right;
            while (predecessor.left != null
                   && predecessor.left != current) {
                predecessor = predecessor.left;
            }
           
            // If left child doesn't point
            // to this node, then put in res
            // this node and make left
            // child point to this node
            if (predecessor.left == null) {
                res.add(current.key);
                predecessor.left = current;
                current = current.right;
            }
           
            // If the left child of inorder predecessor
            // already points to this node
            else {
                predecessor.left = null;
                current = current.left;
            }
        }
    }
   
    // reverse the res
    Collections.reverse(res);
    return res;
}
   
// Driver program
public static void main(String[] args)
{
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(20);
    root.right = new TreeNode(30);
    root.right.left = new TreeNode(40);
    root.right.right = new TreeNode(50);
   
    System.out.print("Morris(postorder) Traversal: ");
    Vector<Integer> ans = postorderTraversal(root);
   
    print(ans);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program  to perform
# Morris Traversal for Postorder
 
# class to create a new tree node
class TreeNode:
    def __init__(self, d):
        self.key = d
        self.left = None
        self.right = None
 
# Function to print list
def print1(ans) :
     
    # Print the vector elements
    for x in ans:
        print(x,end=" ")
     
# Postorder traversal
# Without recursion and without stack
def postorderTraversal(root) :
 
    res=[]
    current = root
 
    while current != None :
     
     
        # If right child is None,
        # put the current node data
        # in res. Move to left child.
        if current.right == None :
            res.append(current.key)
            current = current.left
         
        else :
            predecessor = current.right
            while predecessor.left != None and predecessor.left != current :
                    predecessor = predecessor.left
             
             
            # If left child doesn't point
            # to this node, then put in res
            # this node and make left
            # child point to this node
            if predecessor.left == None:
                res.append(current.key)
                predecessor.left = current
                current = current.right
             
             
            # If the left child of inorder predecessor
            # already points to this node
            else :
                predecessor.left = None
                current = current.left
             
     
    # reverse the res
    res.reverse()
    return res
 
# Driver Code
if __name__ == '__main__':
     
    root = TreeNode(10)
    root.left = TreeNode(20)
    root.right = TreeNode(30)
    root.right.left = TreeNode(40)
    root.right.right = TreeNode(50)
     
    print("Morris(postorder) Traversal: ",end='')
    ans = postorderTraversal(root)
     
    print1(ans)
 
    # This code is contributed by jana_sayantan.

// C# program to perform
// Morris Traversal for Postorder
using System;
using System.Collections.Generic;
 
public class GFG {
 
  public class TreeNode {
    public int key;
    public TreeNode left;
    public TreeNode right;
 
    public TreeNode(int data) {
      key = data;
      left = null;
      right = null;
    }
  };
 
  // Function to print vector
  static void print(List<int> ans)
  {
     
    // Print the vector elements
    foreach (int x in ans) {
      Console.Write(x + " ");
    }
  }
 
  // Postorder traversal
  // Without recursion and without stack
  static List<int> postorderTraversal(TreeNode root) {
    List<int> res = new List<int>();
    TreeNode current = root;
 
    while (current != null) {
 
      // If right child is null,
      // put the current node data
      // in res. Move to left child.
      if (current.right == null) {
        res.Add(current.key);
        current = current.left;
      } else {
        TreeNode predecessor = current.right;
        while (predecessor.left != null && predecessor.left != current) {
          predecessor = predecessor.left;
        }
 
        // If left child doesn't point
        // to this node, then put in res
        // this node and make left
        // child point to this node
        if (predecessor.left == null) {
          res.Add(current.key);
          predecessor.left = current;
          current = current.right;
        }
 
        // If the left child of inorder predecessor
        // already points to this node
        else {
          predecessor.left = null;
          current = current.left;
        }
      }
    }
 
    // reverse the res
    res.Reverse();
    return res;
  }
 
  // Driver program
  public static void Main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(20);
    root.right = new TreeNode(30);
    root.right.left = new TreeNode(40);
    root.right.right = new TreeNode(50);
 
    Console.Write("Morris(postorder) Traversal: ");
    List<int> ans = postorderTraversal(root);
 
    print(ans);
  }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to perform
// Morris Traversal for Postorder
class TreeNode {
 
    constructor(data)
    {
        this.key = data;
        this.left = null;
        this.right = null;
    }
}
 
// Function to print vector
function print(ans)
{
 
    // Print the vector elements
    for (let x of ans) {
        document.write(x," ");
    }
}
 
// Postorder traversal
// Without recursion and without stack
function postorderTraversal(root)
{
    let res=[];
    let current = root;
 
    while (current != null)
    {
     
        // If right child is null,
        // put the current node data
        // in res. Move to left child.
        if (current.right == null) {
            res.push(current.key);
            current = current.left;
        }
        else {
            let predecessor = current.right;
            while (predecessor.left != null
                   && predecessor.left != current) {
                predecessor = predecessor.left;
            }
             
            // If left child doesn't point
            // to this node, then put in res
            // this node and make left
            // child point to this node
            if (predecessor.left == null) {
                res.push(current.key);
                predecessor.left = current;
                current = current.right;
            }
             
            // If the left child of inorder predecessor
            // already points to this node
            else {
                predecessor.left = null;
                current = current.left;
            }
        }
    }
     
    // reverse the res
    res.reverse();
    return res;
}
 
// Driver program
 
let root = new TreeNode(10);
root.left = new TreeNode(20);
root.right = new TreeNode(30);
root.right.left = new TreeNode(40);
root.right.right = new TreeNode(50);
   
document.write("Morris(postorder) Traversal: ");
let ans = postorderTraversal(root);
   
print(ans);
 
// This code is contributed by shinjanpatra
 
</script>

Morris(postorder) Traversal: 20 40 50 30 10 

 Complejidad temporal: O(N)
Espacio auxiliar: O(N)