给定二叉树的顺序和前序遍历，打印后序遍历。
null
例子：
Input:Inorder traversal in[] = {4, 2, 5, 1, 3, 6}Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}Output:Postorder traversal is {4, 5, 2, 6, 3, 1}
上面示例中的遍历表示以下树
1 / 2 3 / 4 5 6
A. 天真法 首先构造树，然后使用简单的递归方法打印所构造树的后序遍历。
我们可以打印后序遍历，而无需构建树 其思想是，根始终是前序遍历中的第一项，它必须是后序遍历中的最后一项。我们首先递归地打印左子树，然后递归地打印右子树。最后，打印root。为了在pre[]和in[]中找到左子树和右子树的边界，我们在in[]中搜索根，在in[]中根之前的所有元素都是左子树的元素，根之后的所有元素都是右子树的元素。在pre[]中，在[]中的根索引之后的所有元素都是右子树的元素。索引之前的元素（包括索引处的元素，不包括第一个元素）是左子树的元素。
C++
// C++ program to print postorder traversal from preorder and inorder traversals #include <iostream> using namespace std; // A utility function to search x in arr[] of size n int search( int arr[], int x, int n) { for ( int i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } // Prints postorder traversal from given inorder and preorder traversals void printPostOrder( int in[], int pre[], int n) { // The first element in pre[] is always root, search it // in in[] to find left and right subtrees int root = search(in, pre[0], n); // If left subtree is not empty, print left subtree if (root != 0) printPostOrder(in, pre + 1, root); // If right subtree is not empty, print right subtree if (root != n - 1) printPostOrder(in + root + 1, pre + root + 1, n - root - 1); // Print root cout << pre[0] << " " ; } // Driver program to test above functions int main() { int in[] = { 4, 2, 5, 1, 3, 6 }; int pre[] = { 1, 2, 4, 5, 3, 6 }; int n = sizeof (in) / sizeof (in[0]); cout << "Postorder traversal " << endl; printPostOrder(in, pre, n); return 0; } |
JAVA
// Java program to print postorder // traversal from preorder and // inorder traversals import java.util.Arrays; class GFG { // A utility function to search x in arr[] of size n static int search( int arr[], int x, int n) { for ( int i = 0 ; i < n; i++) if (arr[i] == x) return i; return - 1 ; } // Prints postorder traversal from // given inorder and preorder traversals static void printPostOrder( int in1[], int pre[], int n) { // The first element in pre[] is // always root, search it in in[] // to find left and right subtrees int root = search(in1, pre[ 0 ], n); // If left subtree is not empty, // print left subtree if (root != 0 ) printPostOrder(in1, Arrays.copyOfRange(pre, 1 , n), root); // If right subtree is not empty, // print right subtree if (root != n - 1 ) printPostOrder(Arrays.copyOfRange(in1, root+ 1 , n), Arrays.copyOfRange(pre, 1 +root, n), n - root - 1 ); // Print root System.out.print( pre[ 0 ] + " " ); } // Driver code public static void main(String args[]) { int in1[] = { 4 , 2 , 5 , 1 , 3 , 6 }; int pre[] = { 1 , 2 , 4 , 5 , 3 , 6 }; int n = in1.length; System.out.println( "Postorder traversal " ); printPostOrder(in1, pre, n); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to print postorder # traversal from preorder and inorder # traversals # A utility function to search x in # arr[] of size n def search(arr, x, n): for i in range (n): if (arr[i] = = x): return i return - 1 # Prints postorder traversal from # given inorder and preorder traversals def printPostOrder(In, pre, n): # The first element in pre[] is always # root, search it in in[] to find left # and right subtrees root = search(In, pre[ 0 ], n) # If left subtree is not empty, # print left subtree if (root ! = 0 ): printPostOrder(In, pre[ 1 :n], root) # If right subtree is not empty, # print right subtree if (root ! = n - 1 ): printPostOrder(In[root + 1 : n], pre[root + 1 : n], n - root - 1 ) # Print root print (pre[ 0 ], end = " " ) # Driver code In = [ 4 , 2 , 5 , 1 , 3 , 6 ] pre = [ 1 , 2 , 4 , 5 , 3 , 6 ] n = len (In) print ( "Postorder traversal " ) printPostOrder(In, pre, n) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to print postorder // traversal from preorder and // inorder traversals using System; class GFG { // A utility function to search x // in []arr of size n static int search( int []arr, int x, int n) { for ( int i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } // Prints postorder traversal from // given inorder and preorder traversals static void printPostOrder( int []in1, int []pre, int n) { // The first element in pre[] is // always root, search it in in[] // to find left and right subtrees int root = search(in1, pre[0], n); // If left subtree is not empty, // print left subtree int []ar; if (root != 0) { ar = new int [n - 1]; Array.Copy(pre, 1, ar, 0, n - 1); printPostOrder(in1, ar, root); } // If right subtree is not empty, // print right subtree if (root != n - 1) { ar = new int [n - (root + 1)]; Array.Copy(in1, root + 1, ar, 0, n - (root + 1)); int []ar1 = new int [n - (root + 1)]; Array.Copy(pre, root + 1, ar1, 0, n - (root + 1)); printPostOrder(ar, ar1, n - root - 1); } // Print root Console.Write(pre[0] + " " ); } // Driver code public static void Main(String []args) { int []in1 = { 4, 2, 5, 1, 3, 6 }; int []pre = { 1, 2, 4, 5, 3, 6 }; int n = in1.Length; Console.WriteLine( "Postorder traversal " ); printPostOrder(in1, pre, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program to print postorder // traversal from preorder and // inorder traversals // A utility function to search x in arr of size n function search(arr , x , n) { for ( var i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } // Prints postorder traversal from // given inorder and preorder traversals function printPostOrder( in1, pre , n) { // The first element in pre is // always root, search it in in // to find left and right subtrees var root = search(in1, pre[0], n); // If left subtree is not empty, // print left subtree if (root != 0) printPostOrder(in1, pre.slice(1, n), root); // If right subtree is not empty, // print right subtree if (root != n - 1) printPostOrder(in1.slice(root+1, n), pre.slice(1+root, n), n - root - 1); // Print root document.write( pre[0] + " " ); } // Driver code var in1 = [ 4, 2, 5, 1, 3, 6 ]; var pre = [ 1, 2, 4, 5, 3, 6 ]; var n = in1.length; document.write( "Postorder traversal <br>" ); printPostOrder(in1, pre, n); // This code contributed by shikhasingrajput </script> |
输出：
Postorder traversal 4 5 2 6 3 1
下面是实现。
C++
// C++ program to print Postorder // traversal from given Inorder // and Preorder traversals. #include <iostream> using namespace std; int preIndex = 0; int search( int arr[], int startIn, int endIn, int data) { int i = 0; for (i = startIn; i < endIn; i++) { if (arr[i] == data) { return i; } } return i; } void printPost( int arr[], int pre[], int inStrt, int inEnd) { if (inStrt > inEnd) { return ; } // Find index of next item in preorder // traversal in inorder. int inIndex = search(arr, inStrt, inEnd,pre[preIndex++]); // traverse left tree printPost(arr, pre, inStrt, inIndex - 1); // traverse right tree printPost(arr, pre, inIndex + 1, inEnd); // print root node at the end of traversal cout << arr[inIndex] << " " ; } // Driver code int main() { int arr[] = {4, 2, 5, 1, 3, 6}; int pre[] = {1, 2, 4, 5, 3, 6}; int len = sizeof (arr)/ sizeof (arr[0]); printPost(arr, pre, 0, len - 1); } // This code is contributed by SHUBHAMSINGH10 |
JAVA
// Java program to print Postorder traversal from given Inorder // and Preorder traversals. public class PrintPost { static int preIndex = 0 ; void printPost( int [] in, int [] pre, int inStrt, int inEnd) { if (inStrt > inEnd) return ; // Find index of next item in preorder traversal in // inorder. int inIndex = search(in, inStrt, inEnd, pre[preIndex++]); // traverse left tree printPost(in, pre, inStrt, inIndex - 1 ); // traverse right tree printPost(in, pre, inIndex + 1 , inEnd); // print root node at the end of traversal System.out.print(in[inIndex] + " " ); } int search( int [] in, int startIn, int endIn, int data) { int i = 0 ; for (i = startIn; i < endIn; i++) if (in[i] == data) return i; return i; } // Driver code public static void main(String ars[]) { int in[] = { 4 , 2 , 5 , 1 , 3 , 6 }; int pre[] = { 1 , 2 , 4 , 5 , 3 , 6 }; int len = in.length; PrintPost tree = new PrintPost(); tree.printPost(in, pre, 0 , len - 1 ); } } |
C#
// C# program to print Postorder // traversal from given Inorder // and Preorder traversals. using System; class GFG { public static int preIndex = 0; public virtual void printPost( int [] arr, int [] pre, int inStrt, int inEnd) { if (inStrt > inEnd) { return ; } // Find index of next item in preorder // traversal in inorder. int inIndex = search(arr, inStrt, inEnd, pre[preIndex++]); // traverse left tree printPost(arr, pre, inStrt, inIndex - 1); // traverse right tree printPost(arr, pre, inIndex + 1, inEnd); // print root node at the end of traversal Console.Write(arr[inIndex] + " " ); } public virtual int search( int [] arr, int startIn, int endIn, int data) { int i = 0; for (i = startIn; i < endIn; i++) { if (arr[i] == data) { return i; } } return i; } // Driver code public static void Main( string [] ars) { int [] arr = new int [] {4, 2, 5, 1, 3, 6}; int [] pre = new int [] {1, 2, 4, 5, 3, 6}; int len = arr.Length; GFG tree = new GFG(); tree.printPost(arr, pre, 0, len - 1); } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to print Postorder // traversal from given Inorder // and Preorder traversals. class GFG { constructor() { this .preIndex = 0; } printPost(arr, pre, inStrt, inEnd) { if (inStrt > inEnd) { return ; } // Find index of next item in preorder // traversal in inorder. var inIndex = this .search(arr, inStrt, inEnd, pre[ this .preIndex++]); // traverse left tree this .printPost(arr, pre, inStrt, inIndex - 1); // traverse right tree this .printPost(arr, pre, inIndex + 1, inEnd); // print root node at the end of traversal document.write(arr[inIndex] + " " ); } search(arr, startIn, endIn, data) { var i = 0; for (i = startIn; i < endIn; i++) { if (arr[i] == data) { return i; } } return i; } } // Driver code var arr = [4, 2, 5, 1, 3, 6]; var pre = [1, 2, 4, 5, 3, 6]; var len = arr.length; var tree = new GFG(); tree.printPost(arr, pre, 0, len - 1); </script> |
输出：
4 5 2 6 3 1
时间复杂性： 上述函数访问阵列中的每个节点。对于每次访问，它都会调用搜索，这需要O（n）个时间。因此，函数的总体时间复杂度为O（n 2. )
可以使用哈希优化上述解决方案。我们使用HashMap存储元素及其索引，以便快速找到元素的索引。
C++
// C++ program to print Postorder traversal from // given Inorder and Preorder traversals. #include<bits/stdc++.h> using namespace std; int preIndex = 0; void printPost( int in[], int pre[], int inStrt, int inEnd, map< int , int > hm) { if (inStrt > inEnd) return ; // Find index of next item in preorder traversal in // inorder. int inIndex = hm[pre[preIndex++]]; // traverse left tree printPost(in, pre, inStrt, inIndex - 1, hm); // traverse right tree printPost(in, pre, inIndex + 1, inEnd, hm); // print root node at the end of traversal cout << in[inIndex] << " " ; } void printPostMain( int in[], int pre[], int n) { map< int , int > hm ; for ( int i = 0; i < n; i++) hm[in[i]] = i; printPost(in, pre, 0, n - 1, hm); } // Driver code int main() { int in[] = { 4, 2, 5, 1, 3, 6 }; int pre[] = { 1, 2, 4, 5, 3, 6 }; int n = sizeof (pre)/ sizeof (pre[0]); printPostMain(in, pre, n); return 0; } // This code is contributed by Arnab Kundu |
JAVA
// Java program to print Postorder traversal from // given Inorder and Preorder traversals. import java.util.*; public class PrintPost { static int preIndex = 0 ; void printPost( int [] in, int [] pre, int inStrt, int inEnd, HashMap<Integer, Integer> hm) { if (inStrt > inEnd) return ; // Find index of next item in preorder traversal in // inorder. int inIndex = hm.get(pre[preIndex++]); // traverse left tree printPost(in, pre, inStrt, inIndex - 1 , hm); // traverse right tree printPost(in, pre, inIndex + 1 , inEnd, hm); // print root node at the end of traversal System.out.print(in[inIndex] + " " ); } void printPostMain( int [] in, int [] pre) { int n = pre.length; HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); for ( int i= 0 ; i<n; i++) hm.put(in[i], i); printPost(in, pre, 0 , n- 1 , hm); } // Driver code public static void main(String ars[]) { int in[] = { 4 , 2 , 5 , 1 , 3 , 6 }; int pre[] = { 1 , 2 , 4 , 5 , 3 , 6 }; PrintPost tree = new PrintPost(); tree.printPostMain(in, pre); } } |
Python3
# Python3 program to print Postorder traversal from # given Inorder and Preorder traversals. def printPost(inn, pre, inStrt, inEnd): global preIndex, hm if (inStrt > inEnd): return # Find index of next item in preorder traversal in # inorder. inIndex = hm[pre[preIndex]] preIndex + = 1 # traverse left tree printPost(inn, pre, inStrt, inIndex - 1 ) # traverse right tree printPost(inn, pre, inIndex + 1 , inEnd) # print root node at the end of traversal print (inn[inIndex], end = " " ) def printPostMain(inn, pre, n): for i in range (n): hm[inn[i]] = i printPost(inn, pre, 0 , n - 1 ) # Driver code if __name__ = = '__main__' : hm = {} preIndex = 0 inn = [ 4 , 2 , 5 , 1 , 3 , 6 ] pre = [ 1 , 2 , 4 , 5 , 3 , 6 ] n = len (pre) printPostMain(inn, pre, n) # This code is contributed by mohit kumar 29 |
C#
// C# program to print Postorder // traversal from given Inorder // and Preorder traversals. using System; class GFG { public static int preIndex = 0; public virtual void printPost( int [] arr, int [] pre, int inStrt, int inEnd) { if (inStrt > inEnd) { return ; } // Find index of next item in preorder // traversal in inorder. int inIndex = search(arr, inStrt, inEnd, pre[preIndex++]); // traverse left tree printPost(arr, pre, inStrt, inIndex - 1); // traverse right tree printPost(arr, pre, inIndex + 1, inEnd); // print root node at the // end of traversal Console.Write(arr[inIndex] + " " ); } public virtual int search( int [] arr, int startIn, int endIn, int data) { int i = 0; for (i = startIn; i < endIn; i++) { if (arr[i] == data) { return i; } } return i; } // Driver code public static void Main( string [] ars) { int [] arr = new int [] {4, 2, 5, 1, 3, 6}; int [] pre = new int [] {1, 2, 4, 5, 3, 6}; int len = arr.Length; GFG tree = new GFG(); tree.printPost(arr, pre, 0, len - 1); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to print // Postorder traversal from given // Inorder and Preorder traversals. let preIndex = 0; function printPost(In, pre, inStrt, inEnd, hm) { if (inStrt > inEnd) return ; // Find index of next item in // preorder traversal in inorder. let inIndex = hm.get(pre[preIndex++]); // Traverse left tree printPost(In, pre, inStrt, inIndex - 1, hm); // Traverse right tree printPost(In, pre, inIndex + 1, inEnd, hm); // Print root node at the end of traversal document.write(In[inIndex] + " " ); } function printPostMain(In, pre) { let n = pre.length; let hm = new Map(); for (let i = 0; i < n; i++) hm.set(In[i], i); printPost(In, pre, 0, n - 1, hm); } // Driver code let In = [ 4, 2, 5, 1, 3, 6 ]; let pre = [ 1, 2, 4, 5, 3, 6 ]; printPostMain(In, pre); // This code is contributed by unknown2108 </script> |
输出：
4 5 2 6 3 1
时间复杂性： O（n） 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
