原文:
给定二叉树的有序遍历和前序遍历，打印后序遍历。
示例:
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}
上例中的 travelsals 代表以下树
1
/ \
2 3
/ \ \
4 5 6
一个天真的方法是先构造树，然后用简单的递归方法打印构造树的后序遍历。
我们不需要构造树就可以打印后序遍历。其思想是，根总是前序遍历中的第一项，它必须是后序遍历中的最后一项。我们先递归打印左子树，然后递归打印右子树。最后，打印根。为了找到 pre[]和 in[]中左右子树的边界，我们在[]中搜索 root in，在[]中 root in 之前的所有元素都是左子树的元素，root 之后的所有元素都是右子树的元素。在 pre[]中，[]中根的索引之后的所有元素都是右子树的元素。索引之前的元素(包括索引处的元素，不包括第一个元素)是左子树的元素。
c
// c program to print postorder traversal from preorder and inorder traversals
#include
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
python 3
# 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
output:
postorder traversal
4 5 2 6 3 1
下面是实现。
c
// c program to print postorder
// traversal from given inorder
// and preorder traversals.
#include
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
java 描述语言
output:
4 5 2 6 3 1
时间复杂度:上述函数访问数组中的每个节点。对于每次访问，它都调用搜索，这需要 o(n)个时间。因此，该功能的整体时间复杂度为 o(n 2
上述pg电子试玩链接的解决方案可以使用哈希进行优化。我们使用一个 hashmap 来存储元素及其索引，这样我们就可以快速找到一个元素的索引。
c
// c program to print postorder traversal from
// given inorder and preorder traversals.
#include
using namespace std;
int preindex = 0;
void printpost(int in[], int pre[], int instrt,
int inend, map 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 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 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 hm = new hashmap();
for (int i=0; i
python 3
# python3 program to prpostorder 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)
# prroot 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
java 描述语言
output:
4 5 2 6 3 1
时间复杂度: o(n)
如果发现有不正确的地方请写评论，或者想分享更多以上讨论话题的信息
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
