Dado un árbol binario y un Node en el árbol binario, encuentre el sucesor Postorder del Node dado.
Examples: Consider the following binary tree 20 / \ 10 26 / \ / \ 4 18 24 27 / \ 14 19 / \ 13 15 Postorder traversal of given tree is 4, 13, 15, 14, 19, 18, 10, 24, 27, 26, 20. Input : 24 Output : 27 Input : 4 Output : 13
Una solución simple es almacenar primero el recorrido posterior al orden del árbol dado en una array, luego buscar linealmente el Node dado e imprimir el Node al lado.
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Una solución eficiente se basa en las siguientes observaciones.
- Si el Node dado es la raíz, entonces el sucesor del orden posterior es NULL, ya que la raíz es la última impresión del Node en un recorrido del orden posterior
- Si el Node dado es el hijo derecho del padre o el hijo derecho del padre es NULL, entonces el padre es el sucesor del orden posterior.
- Si el Node dado es el hijo izquierdo del padre y el hijo derecho del padre no es NULL, entonces el sucesor del orden posterior es el Node más a la izquierda del subárbol derecho del padre.
C++
// CPP program to find postorder successor of // given node. #include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int value; }; // Utility function to create a new node with // given value. struct Node* newNode(int value) { Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->value = value; return temp; } Node* postorderSuccessor(Node* root, Node* n) { // Root has no successor in postorder // traversal if (n == root) return NULL; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node* parent = n->parent; if (parent->right == NULL || parent->right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node* curr = parent->right; while (curr->left != NULL) curr = curr->left; return curr; } // Driver code int main() { struct Node* root = newNode(20); root->parent = NULL; root->left = newNode(10); root->left->parent = root; root->left->left = newNode(4); root->left->left->parent = root->left; root->left->right = newNode(18); root->left->right->parent = root->left; root->right = newNode(26); root->right->parent = root; root->right->left = newNode(24); root->right->left->parent = root->right; root->right->right = newNode(27); root->right->right->parent = root->right; root->left->right->left = newNode(14); root->left->right->left->parent = root->left->right; root->left->right->left->left = newNode(13); root->left->right->left->left->parent = root->left->right->left; root->left->right->left->right = newNode(15); root->left->right->left->right->parent = root->left->right->left; root->left->right->right = newNode(19); root->left->right->right->parent = root->left->right; struct Node* res = postorderSuccessor(root, root->left->right->right); if (res) printf("Postorder successor of %d is %d\n", root->left->right->right->value, res->value); else printf("Postorder successor of %d is NULL\n", root->left->right->right->value); return 0; }
Java
// Java program to find postorder successor of // given node. import java.util.*; class GfG { static class Node { Node left, right, parent; int value; } // Utility function to create a new node with // given value. static Node newNode(int value) { Node temp = new Node(); temp.left = null; temp.right = null; temp.parent = null; temp.value = value; return temp; } static Node postorderSuccessor(Node root, Node n) { // Root has no successor in postorder // traversal if (n == root) return null; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node curr = parent.right; while (curr.left != null) curr = curr.left; return curr; } // Driver code public static void main(String[] args) { Node root = newNode(20); root.parent = null; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; Node res = postorderSuccessor(root, root.left.right.right); if (res != null) System.out.println("Postorder successor of "+ root.left.right.right.value + " is "+ res.value); else System.out.println("Postorder successor of " + root.left.right.right.value + " is NULL"); } }
Python3
""" Python3 program to find postorder successor of a node in Binary Tree.""" # A Binary Tree Node # Utility function to create a new tree node class newNode: # Constructor to create a new node def __init__(self, data): self.value = data self.left = None self.right = None self.parent=None def postorderSuccessor(root, n) : # Root has no successor in postorder # traversal if (n == root): return None # If given node is right child of its # parent or parent's right is empty, # then parent is postorder successor. parent = n.parent if (parent.right == None or parent.right == n): return parent # In all other cases, find the leftmost # child in right subtree of parent. curr = parent.right while (curr.left != None): curr = curr.left return curr # Driver Code if __name__ == '__main__': root = newNode(20) root.parent = None root.left = newNode(10) root.left.parent = root root.left.left = newNode(4) root.left.left.parent = root.left root.left.right = newNode(18) root.left.right.parent = root.left root.right = newNode(26) root.right.parent = root root.right.left = newNode(24) root.right.left.parent = root.right root.right.right = newNode(27) root.right.right.parent = root.right root.left.right.left = newNode(14) root.left.right.left.parent = root.left.right root.left.right.left.left = newNode(13) root.left.right.left.left.parent = root.left.right.left root.left.right.left.right = newNode(15) root.left.right.left.right.parent = root.left.right.left root.left.right.right = newNode(19) root.left.right.right.parent = root.left.right res = postorderSuccessor(root, root.left.right.right) if (res) : print("postorder successor of", root.left.right.right.value, "is", res.value) else: print("postorder successor of", root.left.right.right.value, "is None") # This code is contributed by SHUBHAMSINGH10
C#
// C# program to find postorder successor of // given node. using System; class GfG { class Node { public Node left, right, parent; public int value; } // Utility function to create // a new node with given value. static Node newNode(int value) { Node temp = new Node(); temp.left = null; temp.right = null; temp.parent = null; temp.value = value; return temp; } static Node postorderSuccessor(Node root, Node n) { // Root has no successor in // postorder traversal if (n == root) return null; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node curr = parent.right; while (curr.left != null) curr = curr.left; return curr; } // Driver code public static void Main(String[] args) { Node root = newNode(20); root.parent = null; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; Node res = postorderSuccessor(root, root.left.right.right); if (res != null) Console.WriteLine("Postorder successor of "+ root.left.right.right.value + " is "+ res.value); else Console.WriteLine("Postorder successor of " + root.left.right.right.value + " is NULL"); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript program to find postorder successor of // given node. class Node { constructor() { this.value = 0; this.left = null; this.right = null; this.parent = null; } } // Utility function to create // a new node with given value. function newNode(value) { var temp = new Node(); temp.left = null; temp.right = null; temp.parent = null; temp.value = value; return temp; } function postorderSuccessor(root, n) { // Root has no successor in // postorder traversal if (n == root) return null; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. var parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. var curr = parent.right; while (curr.left != null) curr = curr.left; return curr; } // Driver code var root = newNode(20); root.parent = null; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; var res = postorderSuccessor(root, root.left.right.right); if (res != null) document.write("Postorder successor of "+ root.left.right.right.value + " is "+ res.value); else document.write("Postorder successor of " + root.left.right.right.value + " is NULL"); // This code is contributed by famously. </script>
Producción:
Postorder successor of 19 is 18
Complejidad de tiempo: O (h) donde h es la altura del
espacio auxiliar del árbol binario dado: O (1) ya que no se usan arrays, pilas, colas.
Publicación traducida automáticamente
Artículo escrito por NayanGadre y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA