给定后序和顺序遍历，构造树。
null
例如：
Input: in[] = {2, 1, 3}post[] = {2, 3, 1}Output: Root of below tree 1 / 2 3 Input: in[] = {4, 8, 2, 5, 1, 6, 3, 7}post[] = {8, 4, 5, 2, 6, 7, 3, 1} Output: Root of below tree 1 / 2 3 / / 4 5 6 7 8
我们已经讨论了这个问题 建筑 树 从按序和按序遍历 .这个想法很相似。 让我们看看从in[]={4,8,2,5,1,6,3,7}和post[]={8,4,5,2,6,7,3,1}构建树的过程 1) 我们首先在post[]中找到最后一个节点。最后一个节点是“1”，我们知道这个值是根，因为根总是出现在后序遍历的末尾。 2) 我们在[]中搜索“1”，以找到根的左子树和右子树。[]中“1”左边的所有内容都在左边的子树中，右边的所有内容都在右边的子树中。
1 / [4, 8, 2, 5] [6, 3, 7]
3) 我们在以下两个方面重复上述过程。 …. b） 在[]={6,3,7}和后[]={6,7,3}中重复 …….将创建的树作为根的正确子级。 …. （a） 在[]={4,8,2,5}和post[]={8,4,5,2}中重复出现。 …….将创建的树作为根的左子级。 下面是上述想法的实施。一个重要的观察结果是，每当我们创建一个新节点时，我们递归地在左子树之前调用右子树，因为我们减少了后序索引的索引。
C++
/* C++ program to construct tree using inorder and postorder traversals */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; Node *left, *right; }; // Utility function to create a new node Node* newNode( int data); /* Prototypes for utility functions */ int search( int arr[], int strt, int end, int value); /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ Node* buildUtil( int in[], int post[], int inStrt, int inEnd, int * pIndex) { // Base case if (inStrt > inEnd) return NULL; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ Node* node = newNode(post[*pIndex]); (*pIndex)--; /* If this node has no children then return */ if (inStrt == inEnd) return node; /* Else find the index of this node in Inorder traversal */ int iIndex = search(in, inStrt, inEnd, node->data); /* Using index in Inorder traversal, construct left and right subtress */ node->right = buildUtil(in, post, iIndex + 1, inEnd, pIndex); node->left = buildUtil(in, post, inStrt, iIndex - 1, pIndex); return node; } // This function mainly initializes index of root // and calls buildUtil() Node* buildTree( int in[], int post[], int n) { int pIndex = n - 1; return buildUtil(in, post, 0, n - 1, &pIndex); } /* Function to find index of value in arr[start...end] The function assumes that value is postsent in in[] */ int search( int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) break ; } return i; } /* Helper function that allocates a new node */ Node* newNode( int data) { Node* node = (Node*) malloc ( sizeof (Node)); node->data = data; node->left = node->right = NULL; return (node); } /* This function is here just to test */ void preOrder(Node* node) { if (node == NULL) return ; printf ( "%d " , node->data); preOrder(node->left); preOrder(node->right); } // Driver code int main() { int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 }; int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 }; int n = sizeof (in) / sizeof (in[0]); Node* root = buildTree(in, post, n); cout << "Preorder of the constructed tree : " ; preOrder(root); return 0; } |
JAVA
// Java program to construct a tree using inorder // and postorder traversals /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { int data; Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class BinaryTree { /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ Node buildUtil( int in[], int post[], int inStrt, int inEnd, int postStrt, int postEnd) { // Base case if (inStrt > inEnd) return null ; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ Node node = new Node(post[postEnd]); /* If this node has no children then return */ if (inStrt == inEnd) return node; int iIndex = search(in, inStrt, inEnd, node.data); /* Using index in Inorder traversal, construct left and right subtress */ node.left = buildUtil( in, post, inStrt, iIndex - 1 , postStrt, postStrt - inStrt + iIndex - 1 ); node.right = buildUtil(in, post, iIndex + 1 , inEnd, postEnd - inEnd + iIndex, postEnd - 1 ); return node; } /* Function to find index of value in arr[start...end] The function assumes that value is postsent in in[] */ int search( int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) break ; } return i; } /* This function is here just to test */ void preOrder(Node node) { if (node == null ) return ; System.out.print(node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver Code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int in[] = new int [] { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 }; int post[] = new int [] { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 }; int n = in.length; Node root = tree.buildUtil(in, post, 0 , n - 1 , 0 , n - 1 ); System.out.println( "Preorder of the constructed tree : " ); tree.preOrder(root); } } // This code has been contributed by Mayank // Jaiswal(mayank_24) |
Python3
# Python3 program to construct tree using # inorder and postorder traversals # Helper function that allocates # a new node class newNode: def __init__( self , data): self .data = data self .left = self .right = None # Recursive function to construct binary # of size n from Inorder traversal in[] # and Postorder traversal post[]. Initial # values of inStrt and inEnd should be # 0 and n -1. The function doesn't do any # error checking for cases where inorder # and postorder do not form a tree def buildUtil(In, post, inStrt, inEnd, pIndex): # Base case if (inStrt > inEnd): return None # Pick current node from Postorder traversal # using postIndex and decrement postIndex node = newNode(post[pIndex[ 0 ]]) pIndex[ 0 ] - = 1 # If this node has no children # then return if (inStrt = = inEnd): return node # Else find the index of this node # in Inorder traversal iIndex = search(In, inStrt, inEnd, node.data) # Using index in Inorder traversal, # construct left and right subtress node.right = buildUtil(In, post, iIndex + 1 , inEnd, pIndex) node.left = buildUtil(In, post, inStrt, iIndex - 1 , pIndex) return node # This function mainly initializes index # of root and calls buildUtil() def buildTree(In, post, n): pIndex = [n - 1 ] return buildUtil(In, post, 0 , n - 1 , pIndex) # Function to find index of value in # arr[start...end]. The function assumes # that value is postsent in in[] def search(arr, strt, end, value): i = 0 for i in range (strt, end + 1 ): if (arr[i] = = value): break return i # This function is here just to test def preOrder(node): if node = = None : return print (node.data,end = " " ) preOrder(node.left) preOrder(node.right) # Driver code if __name__ = = '__main__' : In = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ] post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] n = len (In) root = buildTree(In, post, n) print ( "Preorder of the constructed tree :" ) preOrder(root) # This code is contributed by PranchalK |
C#
// C# program to construct a tree using // inorder and postorder traversals using System; /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } // Class Index created to implement // pass by reference of Index public class Index { public int index; } class GFG { /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ public virtual Node buildUtil( int [] @ in , int [] post, int inStrt, int inEnd, Index pIndex) { // Base case if (inStrt > inEnd) { return null ; } /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ Node node = new Node(post[pIndex.index]); (pIndex.index)--; /* If this node has no children then return */ if (inStrt == inEnd) { return node; } /* Else find the index of this node in Inorder traversal */ int iIndex = search(@ in , inStrt, inEnd, node.data); /* Using index in Inorder traversal, construct left and right subtress */ node.right = buildUtil(@ in , post, iIndex + 1, inEnd, pIndex); node.left = buildUtil(@ in , post, inStrt, iIndex - 1, pIndex); return node; } // This function mainly initializes // index of root and calls buildUtil() public virtual Node buildTree( int [] @ in , int [] post, int n) { Index pIndex = new Index(); pIndex.index = n - 1; return buildUtil(@ in , post, 0, n - 1, pIndex); } /* Function to find index of value in arr[start...end]. The function assumes that value is postsent in in[] */ public virtual int search( int [] arr, int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) { break ; } } return i; } /* This function is here just to test */ public virtual void preOrder(Node node) { if (node == null ) { return ; } Console.Write(node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver Code public static void Main( string [] args) { GFG tree = new GFG(); int [] @ in = new int [] {4, 8, 2, 5, 1, 6, 3, 7}; int [] post = new int [] {8, 4, 5, 2, 6, 7, 3, 1}; int n = @ in .Length; Node root = tree.buildTree(@ in , post, n); Console.WriteLine( "Preorder of the constructed tree : " ); tree.preOrder(root); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to construct a tree using inorder // and postorder traversals /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { constructor(data) { this .data = data; this .left = this .right = null ; } } /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ function buildUtil(In, post, inStrt, inEnd, postStrt, postEnd) { // Base case if (inStrt > inEnd) return null ; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ let node = new Node(post[postEnd]); /* If this node has no children then return */ if (inStrt == inEnd) return node; let iIndex = search(In, inStrt, inEnd, node.data); /* Using index in Inorder traversal, construct left and right subtress */ node.left = buildUtil( In, post, inStrt, iIndex - 1, postStrt, postStrt - inStrt + iIndex - 1); node.right = buildUtil(In, post, iIndex + 1, inEnd, postEnd - inEnd + iIndex, postEnd - 1); return node; } /* Function to find index of value in arr[start...end] The function assumes that value is postsent in in[] */ function search(arr,strt,end,value) { let i; for (i = strt; i <= end; i++) { if (arr[i] == value) break ; } return i; } /* This function is here just to test */ function preOrder(node) { if (node == null ) return ; document.write(node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver Code let In=[4, 8, 2, 5, 1, 6, 3, 7]; let post=[8, 4, 5, 2, 6, 7, 3, 1]; let n = In.length; let root = buildUtil(In, post, 0, n - 1, 0, n - 1); document.write( "Preorder of the constructed tree : <br>" ); preOrder(root); // This code is contributed by unknown2108 </script> |
输出
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
时间复杂性： O（n） 2. )
优化方法： 我们可以使用哈希（C++中的无序排序映射或java中的HashMap）来优化上述解决方案。我们将按序遍历的索引存储在哈希表中。因此，如果给定树中的元素不重复，则可以进行O（1）次搜索。
C++
/* C++ program to construct tree using inorder and postorder traversals */ #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; Node *left, *right; }; // Utility function to create a new node Node* newNode( int data); /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ Node* buildUtil( int in[], int post[], int inStrt, int inEnd, int * pIndex, unordered_map< int , int >& mp) { // Base case if (inStrt > inEnd) return NULL; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ int curr = post[*pIndex]; Node* node = newNode(curr); (*pIndex)--; /* If this node has no children then return */ if (inStrt == inEnd) return node; /* Else find the index of this node in Inorder traversal */ int iIndex = mp[curr]; /* Using index in Inorder traversal, construct left and right subtress */ node->right = buildUtil(in, post, iIndex + 1, inEnd, pIndex, mp); node->left = buildUtil(in, post, inStrt, iIndex - 1, pIndex, mp); return node; } // This function mainly creates an unordered_map, then // calls buildTreeUtil() struct Node* buildTree( int in[], int post[], int len) { // Store indexes of all items so that we // we can quickly find later unordered_map< int , int > mp; for ( int i = 0; i < len; i++) mp[in[i]] = i; int index = len - 1; // Index in postorder return buildUtil(in, post, 0, len - 1, &index, mp); } /* Helper function that allocates a new node */ Node* newNode( int data) { Node* node = (Node*) malloc ( sizeof (Node)); node->data = data; node->left = node->right = NULL; return (node); } /* This function is here just to test */ void preOrder(Node* node) { if (node == NULL) return ; printf ( "%d " , node->data); preOrder(node->left); preOrder(node->right); } // Driver code int main() { int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 }; int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 }; int n = sizeof (in) / sizeof (in[0]); Node* root = buildTree(in, post, n); cout << "Preorder of the constructed tree : " ; preOrder(root); return 0; } |
JAVA
/* Java program to construct tree using inorder and postorder traversals */ import java.util.*; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left, right; }; // Utility function to create a new node /* Helper function that allocates a new node */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ static Node buildUtil( int in[], int post[], int inStrt, int inEnd) { // Base case if (inStrt > inEnd) return null ; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ int curr = post[index]; Node node = newNode(curr); (index)--; /* If this node has no children then return */ if (inStrt == inEnd) return node; /* Else find the index of this node in Inorder traversal */ int iIndex = mp.get(curr); /* Using index in Inorder traversal, con left and right subtress */ node.right = buildUtil(in, post, iIndex + 1 , inEnd); node.left = buildUtil(in, post, inStrt, iIndex - 1 ); return node; } static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); static int index; // This function mainly creates an unordered_map, then // calls buildTreeUtil() static Node buildTree( int in[], int post[], int len) { // Store indexes of all items so that we // we can quickly find later for ( int i = 0 ; i < len; i++) mp.put(in[i], i); index = len - 1 ; // Index in postorder return buildUtil(in, post, 0 , len - 1 ); } /* This function is here just to test */ static void preOrder(Node node) { if (node == null ) return ; System.out.printf( "%d " , node.data); preOrder(node.left); preOrder(node.right); } // Driver code public static void main(String[] args) { int in[] = { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 }; int post[] = { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 }; int n = in.length; Node root = buildTree(in, post, n); System.out.print( "Preorder of the constructed tree : " ); preOrder(root); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to construct tree using inorder # and postorder traversals # A binary tree node has data, pointer to left # child and a pointer to right child class Node: def __init__( self , x): self .data = x self .left = None self .right = None # Recursive function to construct binary of size n # from Inorder traversal in[] and Postorder traversal # post[]. Initial values of inStrt and inEnd should # be 0 and n -1. The function doesn't do any error # checking for cases where inorder and postorder # do not form a tree def buildUtil(inn, post, innStrt, innEnd): global mp, index # Base case if (innStrt > innEnd): return None # Pick current node from Postorder traversal # using postIndex and decrement postIndex curr = post[index] node = Node(curr) index - = 1 # If this node has no children then return if (innStrt = = innEnd): return node # Else find the index of this node inn # Inorder traversal iIndex = mp[curr] # Using index inn Inorder traversal, # construct left and right subtress node.right = buildUtil(inn, post, iIndex + 1 , innEnd) node.left = buildUtil(inn, post, innStrt, iIndex - 1 ) return node # This function mainly creates an unordered_map, # then calls buildTreeUtil() def buildTree(inn, post, lenn): global index # Store indexes of all items so that we # we can quickly find later for i in range (lenn): mp[inn[i]] = i # Index in postorder index = lenn - 1 return buildUtil(inn, post, 0 , lenn - 1 ) # This function is here just to test def preOrder(node): if (node = = None ): return print (node.data, end = " " ) preOrder(node.left) preOrder(node.right) # Driver Code if __name__ = = '__main__' : inn = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ] post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] n = len (inn) mp, index = {}, 0 root = buildTree(inn, post, n) print ( "Preorder of the constructed tree :" ) preOrder(root) # This code is contributed by mohit kumar 29 |
C#
/* C# program to construct tree using inorder and postorder traversals */ using System; using System.Collections.Generic; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left, right; }; // Utility function to create a new node /* Helper function that allocates a new node */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ static Node buildUtil( int []init, int []post, int inStrt, int inEnd) { // Base case if (inStrt > inEnd) return null ; /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ int curr = post[index]; Node node = newNode(curr); (index)--; /* If this node has no children then return */ if (inStrt == inEnd) return node; /* Else find the index of this node in Inorder traversal */ int iIndex = mp[curr]; /* Using index in Inorder traversal, con left and right subtress */ node.right = buildUtil(init, post, iIndex + 1, inEnd); node.left = buildUtil(init, post, inStrt, iIndex - 1); return node; } static Dictionary< int , int > mp = new Dictionary< int , int >(); static int index; // This function mainly creates an unordered_map, then // calls buildTreeUtil() static Node buildTree( int []init, int []post, int len) { // Store indexes of all items so that we // we can quickly find later for ( int i = 0; i < len; i++) mp.Add(init[i], i); index = len - 1; // Index in postorder return buildUtil(init, post, 0, len - 1 ); } /* This function is here just to test */ static void preOrder(Node node) { if (node == null ) return ; Console.Write( node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver code public static void Main(String[] args) { int []init = { 4, 8, 2, 5, 1, 6, 3, 7 }; int []post = { 8, 4, 5, 2, 6, 7, 3, 1 }; int n = init.Length; Node root = buildTree(init, post, n); Console.Write( "Preorder of the constructed tree : " ); preOrder(root); } } // This code is contributed by Rajput-Ji |
Javascript
<script> /* JavaScript program to construct tree using inorder and postorder traversals */ /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } // Utility function to create a new node /* Helper function that allocates a new node */ function newNode(data) { var node = new Node(); node.data = data; node.left = node.right = null ; return node; } /* Recursive function to construct binary of size n from Inorder traversal in[] and Postorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ function buildUtil(init, post, inStrt, inEnd) { // Base case if (inStrt > inEnd) { return null ; } /* Pick current node from Postorder traversal using postIndex and decrement postIndex */ var curr = post[index]; var node = newNode(curr); index--; /* If this node has no children then return */ if (inStrt == inEnd) { return node; } /* Else find the index of this node in Inorder traversal */ var iIndex = mp[curr]; /* Using index in Inorder traversal, con left and right subtress */ node.right = buildUtil(init, post, iIndex + 1, inEnd); node.left = buildUtil(init, post, inStrt, iIndex - 1); return node; } var mp = {}; var index; // This function mainly creates an unordered_map, then // calls buildTreeUtil() function buildTree(init, post, len) { // Store indexes of all items so that we // we can quickly find later for ( var i = 0; i < len; i++) { mp[init[i]] = i; } index = len - 1; // Index in postorder return buildUtil(init, post, 0, len - 1); } /* This function is here just to test */ function preOrder(node) { if (node == null ) { return ; } document.write(node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver code var init = [4, 8, 2, 5, 1, 6, 3, 7]; var post = [8, 4, 5, 2, 6, 7, 3, 1]; var n = init.length; var root = buildTree(init, post, n); document.write( "Preorder of the constructed tree : <br>" ); preOrder(root); </script> |
输出
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
时间复杂性： O（n）
另一种方法 :
使用堆栈和集合而不使用递归。
以下是上述理念的实施情况：
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; Node *left, *right; Node( int x) { data = x; left = right = NULL; } }; /*Tree building function*/ Node *buildTree( int in[], int post[], int n) { // Create Stack of type Node* stack<Node*> st; // Create Set of type Node* set<Node*> s; // Initialise postIndex with n - 1 int postIndex = n - 1; // Initialise root with NULL Node* root = NULL; for ( int p = n - 1, i = n - 1; p>=0) { // Initialise node with NULL Node* node = NULL; // Run do-while loop do { // Initialise node with // new Node(post[p]); node = new Node(post[p]); // Check is root is // equal to NULL if (root == NULL) { root = node; } // If size of set // is greater than 0 if (st.size() > 0) { // If st.top() is present in the // set s if (s.find(st.top()) != s.end()) { s.erase(st.top()); st.top()->left = node; st.pop(); } else { st.top()->right = node; } } st.push(node); } while (post[p--] != in[i] && p >=0); node = NULL; // If the stack is not empty and // st.top()->data is equal to in[i] while (st.size() > 0 && i>=0 && st.top()->data == in[i]) { node = st.top(); // Pop elements from stack st.pop(); i--; } // if node not equal to NULL if (node != NULL) { s.insert(node); st.push(node); } } // Return root return root; } /* for print preOrder Traversal */ void preOrder(Node* node) { if (node == NULL) return ; printf ( "%d " , node->data); preOrder(node->left); preOrder(node->right); } // Driver Code int main() { int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 }; int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 }; int n = sizeof (in) / sizeof (in[0]); // Function Call Node* root = buildTree(in, post, n); cout << "Preorder of the constructed tree : "; // Function Call for preOrder preOrder(root); return 0; } |
JAVA
// Java program for above approach import java.io.*; import java.util.*; class GFG { // Node class static class Node { int data; Node left, right; // Constructor Node( int x) { data = x; left = right = null ; } } // Tree building function static Node buildTree( int in[], int post[], int n) { // Create Stack of type Node* Stack<Node> st = new Stack<>(); // Create HashSet of type Node* HashSet<Node> s = new HashSet<>(); // Initialise postIndex with n - 1 int postIndex = n - 1 ; // Initialise root with null Node root = null ; for ( int p = n - 1 , i = n - 1 ; p >= 0 :winking_face: { // Initialise node with NULL Node node = null ; // Run do-while loop do { // Initialise node with // new Node(post[p]); node = new Node(post[p]); // Check is root is // equal to NULL if (root == null ) { root = node; } // If size of set // is greater than 0 if (st.size() > 0 ) { // If st.peek() is present in the // set s if (s.contains(st.peek())) { s.remove(st.peek()); st.peek().left = node; st.pop(); } else { st.peek().right = node; } } st.push(node); } while (post[p--] != in[i] && p >= 0 ); node = null ; // If the stack is not empty and // st.top().data is equal to in[i] while (st.size() > 0 && i >= 0 && st.peek().data == in[i]) { node = st.peek(); // Pop elements from stack st.pop(); i--; } // If node not equal to NULL if (node != null ) { s.add(node); st.push(node); } } // Return root return root; } // For print preOrder Traversal static void preOrder(Node node) { if (node == null ) return ; System.out.printf( "%d " , node.data); preOrder(node.left); preOrder(node.right); } // Driver Code public static void main(String[] args) { int in[] = { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 }; int post[] = { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 }; int n = in.length; // Function Call Node root = buildTree(in, post, n); System.out.print( "Preorder of the constructed tree : " ); // Function Call for preOrder preOrder(root); } } // This code is contributed by sujitmeshram |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG { // Node class public class Node { public int data; public Node left, right; // Constructor public Node( int x) { data = x; left = right = null ; } } // Tree building function static Node buildTree( int []init, int []post, int n) { // Create Stack of type Node* Stack<Node> st = new Stack<Node>(); // Create HashSet of type Node* HashSet<Node> s = new HashSet<Node>(); // Initialise postIndex with n - 1 int postIndex = n - 1; // Initialise root with null Node root = null ; for ( int p = n - 1, i = n - 1; p >= 0;) { // Initialise node with NULL Node node = null ; // Run do-while loop do { // Initialise node with // new Node(post[p]); node = new Node(post[p]); // Check is root is // equal to NULL if (root == null ) { root = node; } // If size of set // is greater than 0 if (st.Count > 0) { // If st.Peek() is present in the // set s if (s.Contains(st.Peek())) { s.Remove(st.Peek()); st.Peek().left = node; st.Pop(); } else { st.Peek().right = node; } } st.Push(node); } while (post[p--] != init[i] && p >= 0); node = null ; // If the stack is not empty and // st.top().data is equal to in[i] while (st.Count > 0 && i >= 0 && st.Peek().data == init[i]) { node = st.Peek(); // Pop elements from stack st.Pop(); i--; } // If node not equal to NULL if (node != null ) { s.Add(node); st.Push(node); } } // Return root return root; } // For print preOrder Traversal static void preOrder(Node node) { if (node == null ) return ; Console.Write(node.data + " " ); preOrder(node.left); preOrder(node.right); } // Driver Code public static void Main(String[] args) { int []init = { 4, 8, 2, 5, 1, 6, 3, 7 }; int []post = { 8, 4, 5, 2, 6, 7, 3, 1 }; int n = init.Length; // Function Call Node root = buildTree(init, post, n); Console.Write( "Preorder of the constructed tree : " ); // Function Call for preOrder preOrder(root); } } // This code is contributed by aashish1995 |
输出
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
本文由 里希 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
