第一行一个整数 n,表示二叉树的大小。
第二行 n 个整数 a_i,表示二叉树的先序遍历数组。
第三行 n 个整数 b_i,表示二叉树的中序遍历数组。
输出一行 n 个整数表示二叉树的后序遍历数组。
3 1 2 3 2 1 3
2 3 1
数据保证合法
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); int[] preorder = new int[N]; int[] inorder = new int[N]; for (int i = 0; i < N; i++) { preorder[i] = input.nextInt(); } for (int i = 0; i < N; i++) { inorder[i] = input.nextInt(); } new Main().buildTree(preorder, inorder); } Map<Integer, Integer> map = new HashMap<>(); int[] preorder; public void buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } build(0, preorder.length-1, 0, inorder.length-1); } private void build(int preStart, int preEnd, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) { return ; } int rootVal = preorder[preStart]; int rootIndex = map.get(rootVal); int leftNum = rootIndex - inStart; build(preStart+1, preStart+leftNum, inStart, rootIndex-1); build(preStart+leftNum+1, preEnd, rootIndex+1, inEnd); System.out.print(rootVal + " "); } }
#include <stdlib.h> #include <stdbool.h> typedef struct BTree{ int num; struct BTree *lc,*rc; }BTree; int k; //标记下个访问的先序结点位置 void CreateBTree(BTree *T,int ordp[],int ordi[],bool visited[],int locate,int n){ if (visited[locate] || locate>=n || locate<0) return; else { visited[locate]=true; int l; //在中序序列中向当前根节点左侧探查,考虑是否生成左子树 for (l=locate-1; l>=0 && !visited[l]; l--) { if (ordi[l]==ordp[k+1]) { BTree *t=(BTree*)malloc(sizeof(BTree)); t->num=ordp[++k]; t->lc=NULL; t->rc=NULL; T->lc=t; CreateBTree(T->lc, ordp, ordi, visited, l, n); break; } } //在中序序列中向当前根节点右侧探查,考虑是否生成右子树 for (l=locate+1; l<n && !visited[l]; l++) { if (ordi[l]==ordp[k+1]) { BTree *t=(BTree*)malloc(sizeof(BTree)); t->num=ordp[++k]; t->lc=NULL; t->rc=NULL; T->rc=t; CreateBTree(T->rc, ordp, ordi, visited, l, n); break; } } } } void PostOrdBTree(BTree *T,BTree *root){ if (!T) return; PostOrdBTree(T->lc, T); PostOrdBTree(T->rc, T); printf("%d",T->num); if (T!=root) printf(" "); } int main(){ int n; while (~scanf("%d",&n)) { int ordp[10001],ordi[10001]; //先序与中序序列数组 int root=0,locate=0; //记录二叉树根节点信息 bool visited[10001]; memset(visited, false, sizeof(visited)); for (int i=0; i<n; i++) { scanf("%d",&ordp[i]); if (i==0) root=ordp[i]; //找到二叉树根节点值 } for (int i=0; i<n; i++) { scanf("%d",&ordi[i]); if (root==ordi[i]) locate=i; //找到二叉树根节点位置 } BTree *T=(BTree*)malloc(sizeof(BTree)); T->num=root; T->lc=NULL; T->rc=NULL; k=0; CreateBTree(T, ordp, ordi, visited, locate, n); PostOrdBTree(T, T); } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; import java.util.Stack; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] params = br.readLine().split(" "); int[] preOrder = new int[n]; for(int i = 0; i < n; i++) preOrder[i] = Integer.parseInt(params[i]); params = br.readLine().split(" "); int[] inOrder = new int[n]; for(int i = 0; i < n; i++) inOrder[i] = Integer.parseInt(params[i]); // 重建二叉树 TreeNode root = buildTree(preOrder, inOrder); // 后续遍历 Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(root); while(!stack1.isEmpty()){ TreeNode node = stack1.pop(); stack2.push(node); if(node.left != null) stack1.push(node.left); if(node.right != null) stack1.push(node.right); } while(!stack2.isEmpty()) System.out.print(stack2.pop().val + " "); } private static TreeNode buildTree(int[] preOrder, int[] inOrder) { if(preOrder.length != inOrder.length || preOrder.length == 0) return null; if(preOrder.length == 1){ return new TreeNode(preOrder[0]); }else{ int rootVal = preOrder[0]; TreeNode root = new TreeNode(rootVal); int idx = indexOf(inOrder, rootVal); root.left = buildTree(Arrays.copyOfRange(preOrder, 1, 1 + idx), Arrays.copyOfRange(inOrder, 0, idx)); root.right = buildTree(Arrays.copyOfRange(preOrder, 1 + idx, preOrder.length), Arrays.copyOfRange(inOrder, idx + 1, inOrder.length)); return root; } } private static int indexOf(int[] arr, int target) { int idx = -1; for(int i = 0; i < arr.length; i++){ if(arr[i] == target){ idx = i; break; } } return idx; } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int size = Integer.parseInt(scanner.nextLine()); List<String> pre = Arrays.asList(scanner.nextLine().split(" ")); List<String> order = Arrays.asList(scanner.nextLine().split(" ")); List<String> post = new ArrayList<>(); coverTree(pre, order, post); for (String s : post) { System.out.print(s+" "); } } private static void coverTree(List<String> pre, List<String> order, List<String> post) { if (pre.isEmpty() || order.isEmpty()) { return; } post.add(0, pre.get(0)); int location = order.indexOf(pre.get(0)); coverTree(pre.subList(location + 1, pre.size()), order.subList(location + 1, order.size()), post); coverTree(pre.subList(1, location + 1), order.subList(0, location), post); } }
#include<bits/stdc++.h> using namespace std; // 无需建树,直接利用树的性质即可,递归解决 void getPost(vector<int>& pre,vector<int>& in,int pre_s,int pre_e,int in_s,int in_e,vector<int>& ans) { if(pre_s>pre_e) return; int root = pre[pre_s]; int index; for(index = in_s;index<=in_e;++index) if(in[index]==root) break; // 根节点 ans.push_back(root); // 处理右子树 getPost(pre,in,pre_s+(index-in_s)+1,pre_e,index+1,in_e,ans); // 处理左子树 getPost(pre,in,pre_s+1,pre_s+index-in_s,in_s,index-1,ans); } int main() { int n; cin>>n; vector<int>ans; vector<int>pre(n); vector<int>in(n); for(int i=0;i<n;++i) cin>>pre[i]; for(int i=0;i<n;++i) cin>>in[i]; getPost(pre,in,0,n-1,0,n-1,ans); for(int i=ans.size()-1;i!=-1;i--) cout<<ans[i]<<" "; return 0; }
import java.util.ArrayList; import java.util.Scanner; public class Main { /** * res: 存放后续遍历的结果 */ public static ArrayList<Integer> res = new ArrayList<>(); /** * 树的结点定义 */ public static class Node { public int val; public Node left; public Node right; public Node(int val, Node left, Node right) { this.val = val; this.left = left; this.right = right; } } /** * 根据先序和中序建树 * @param pre 先序遍历数组 * @param in 后序遍历数组 * @param preL 先序子树左边界 * @param preR 先序子树右边界 * @param inL 中序子树左边界 * @param inR 中序子树有边界 * @return 子树根节点,最后一次回溯是树的根节点 */ public static Node create(int[] pre, int[] in, int preL, int preR, int inL, int inR) { if (preL > preR) { return null; } Node node = new Node(pre[preL], null, null); // 根据先序和中序确定左右子树的根节点在中序遍历的位置 int mid; for (mid = inL; pre[preL] != in[mid]; mid++); // 构建左子树 node.left = create(pre, in, preL+1, preL+mid-inL, inL, mid-1); // 构建右子树 node.right = create(pre, in, preL+mid-inL+1, preR, mid+1, inR); return node; } // 后序遍历 public static void postOrder(Node node) { if (node != null) { postOrder(node.left); postOrder(node.right); res.add(node.val); } } public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); int[] pre = new int[N]; int[] in = new int[N]; for (int i = 0; i < N; i++) { pre[i] = input.nextInt(); } for (int i = 0; i < N; i++) { in[i] = input.nextInt(); } Node node = create(pre, in, 0, N-1, 0, N-1); postOrder(node); for (int i = 0; i < res.size(); i++) { System.out.print(res.get(i)); if (i != res.size()-1) { System.out.print(" "); } } } }
import java.util.*; public class Main { int index = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] pre = new int[n]; int[] in = new int[n]; int[] end = new int[n]; //map存储中序遍历中各结点对应的索引 Map<Integer,Integer> map = new HashMap<>(); for(int i=0; i<n; i++) pre[i] = scanner.nextInt(); for(int i=0; i<n; i++){ in[i] = scanner.nextInt(); map.put(in[i], i); } //先将根结点放到最末尾,因为递归遍历左右子树完成后会把根节点返回 //故在此先将根节点放到正确位置 end[n-1] = pre[0]; //递归遍历左右子树 new Main().endOrder(pre, 0, n-1, in, 0, n-1, end, map); //打印后序遍历结果 for(int x : end) System.out.print(x+" "); } public int endOrder(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd, int[] end, Map<Integer,Integer> map){ if(preStart > preEnd) return 0; //节点只有1个直接返回 if(preStart == preEnd) return pre[preStart]; //获取前序遍历开始点在中序遍历中的索引 int k = map.get(pre[preStart]); //左子树长度 int length = k - inStart; //递归遍历左子树 int left = endOrder(pre, preStart+1, preStart+length, in, inStart, k-1, end, map); //left不为空即左子树不为空 if(left != 0) end[index++] = left; //递归遍历右子树 int right = endOrder(pre, preStart+length+1, preEnd, in, k+1, inEnd, end, map); //right不为空即右子树不为空 if(right != 0) end[index++] = right; //遍历结束左右子树后返回根节点 return pre[preStart]; } }
#建立后序遍历序列 def getLast(pre, mid): #如果只有一个节点 #直接返回 if len(pre) <= 1: return pre #先序遍历的第一个节点是根节点 root = pre[0] #划分左右子树 index = mid.index(root) preLeft = pre[1:index + 1] preRight = pre[index + 1:] midLeft = mid[:index] midRight = mid[index + 1:] #后序遍历的顺序是左右根 return getLast(preLeft, midLeft) + getLast(preRight, midRight) + [root] if __name__ == '__main__': #读入数据 n = int(input()) pre = input() pre = pre.split() mid = input() mid = mid.split() #建立后序遍历序列 last = getLast(pre, mid) print(' '.join(last))
#include <stdio.h> #include <stdlib.h> typedef struct { int val; int l_child, r_child; } TreeNodeInfo, *INFO; TreeNodeInfo infos[10010]; // 全局区 int createTree(int* pre, int* inorder, int i, int j, int n) { // recursion exit condition if (n <= 0) return 0; if (n == 1) return *(pre + i); int k = j; while (*(inorder + k) != *(pre + i)) ++k; int l = k - j; infos[*(pre + i)].l_child = createTree(pre, inorder, i + 1, j, l); infos[*(pre + i)].r_child = createTree(pre, inorder, i + 1 + l, k + 1, n - 1 - l); return *(pre + i); } void postorder(INFO infos, int index) { if (!index) return; postorder(infos, infos[index].l_child); postorder(infos, infos[index].r_child); fprintf(stdout, "%d ", index); } int main(int argc, char* argv[]) { int n; fscanf(stdin, "%d", &n); int i, pre[n], inorder[n]; for (i = 0; i < n; ++i) fscanf(stdin, "%d", pre + i); for (i = 0; i < n; ++i) fscanf(stdin, "%d", inorder + i); createTree(pre, inorder, 0, 0, n); postorder(infos, *pre); return 0; }
import java.util.Scanner; import java.util.Map; import java.util.HashMap; public class Main { private static int posIndex; private static Map<Integer, Integer> map = null; private static int[] pos = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); map = new HashMap<>(); int n = sc.nextInt(); int[] pre = new int[n]; int[] in = new int[n]; for (int i = 0; i < n; i++) { pre[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { in[i] = sc.nextInt(); map.put(in[i], i); } pos = new int[n]; posIndex = n - 1; process(pre, 0, n - 1, in, 0, n - 1); for (int i = 0; i < n; i++) { if (i != 0) { System.out.print(" "); } System.out.print(pos[i]); } } public static void process(int[] pre, int preL, int preR, int[] in, int inL, int inR) { if (preL > preR || inL > inR) { return; } int root = pre[preL]; pos[posIndex--] = root; int k = map.get(root); int leftSize = k - inL, rightSize = inR - k; process(pre, preL + leftSize + 1, preR, in, k + 1, inR); process(pre, preL + 1, preL + leftSize, in, inL, k - 1); } }
#include <iostream> #include <cstdio> #include <cstring> #include <bits/stdc++.h> using namespace std; #define maxn 10010 int n; int in[maxn], pre[maxn], post[maxn], stk[maxn]; bool visited[maxn]; int main(){ while(~scanf("%d", &n)){ for(int i = 0; i < n; ++i) scanf("%d", &(pre[i])); for(int i = 0; i < n; ++i) scanf("%d", &(in[i])); memset(visited, false, sizeof(bool)*maxn); int stkcur = 0, incur = -1, precur = 0, postcur = 0; while(precur < n){ stk[stkcur] = pre[precur]; visited[pre[precur]] = true; ++stkcur, ++precur; while(incur+1<n && visited[in[incur+1]]){ while(stkcur > 0 && stk[stkcur-1] != in[incur+1]) post[postcur++] = stk[--stkcur]; ++incur; } } while(stkcur>0) post[postcur++] = stk[--stkcur]; for(int i = 0; i < postcur; ++i) printf(" %d"+!i, post[i]); printf("\n"); } return 0; }
利用的是根据前序和中序还原树的思路求解的该问题,从右向左还原后序遍历数组
def setPos(preorder, inorder, posorder, si): if len(inorder)==0&nbs***bsp;si < 0: return si data = preorder[0] mid = inorder.index(data) posorder[si] = data si = si-1 si = setPos(preorder[mid+1:], inorder[mid+1:], posorder, si) si = setPos(preorder[1:mid+1], inorder[0:mid], posorder, si) return si n = int(input()) prorder = list(map(int, input().split())) inorder = list(map(int, input().split())) posorder = n*[''] s = setPos(prorder, inorder, posorder, n-1) for i in range(n): print(posorder[i], end=' ')
n=int(input()) preOrder=list(map(int,input().split())) inOrder=list(map(int,input().split())) def postOrder(preOrder,inOrder): if len(preOrder)==1&nbs***bsp;len(preOrder)==0: return preOrder ind=inOrder.index(preOrder[0]) left=postOrder(preOrder[1:1+ind],inOrder[:ind]) right=postOrder(preOrder[1+ind:],inOrder[ind+1:]) return left+right+[preOrder[0]] po=postOrder(preOrder,inOrder) print(' '.join(map(str,po)))
#include<iostream> #include<vector> #include <algorithm> using namespace std; void getLRN(vector<int>pre,vector<int>mid,int num){ //根据num值来区分各种特殊情况,比如缺少某些子树 if(num==1){ cout<<pre[0]<<" "; }else if(num==2){ if(pre[0]==mid[0]) cout<<pre[1]<<" "<<pre[0]<<" "; else cout<<mid[0]<<" "<<mid[1]<<" "; }else if(num!=0){ int root = pre[0]; int p; for(p=0;p<num;p++){ if(mid[p]==root) break; } vector<int>pr1,pr2,mid1,mid2; if(p>0){ pr1.assign(pre.begin()+1,pre.begin()+p+1); mid1.assign(mid.begin(),mid.begin()+p+1); } if(num-p-1>0){ pr2.assign(pre.begin()+p+1,pre.begin()+num); mid2.assign(mid.begin()+p+1,mid.begin()+num); } getLRN(pr1,mid1,p); getLRN(pr2,mid2,num-p-1); cout<<pre[0]<<" "; } } int main(){ int num; cin>>num; vector<int>pre; vector<int>mid; for(int i=0;i<num;i++){ int data1; cin>>data1; pre.push_back(data1); } for(int j=0;j<num;j++){ int data2; cin>>data2; mid.push_back(data2); } getLRN(pre,mid,num); return 0; }
import java.util.*; public class Main { static int[] preArr; static int[] inArr; static int[] arr; static Map<Integer, Integer> map; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); preArr = new int[n]; inArr = new int[n]; for(int i=0;i<n;i++){ preArr[i] = scanner.nextInt(); } map = new HashMap<Integer, Integer>(); for(int i=0;i<n;i++){ inArr[i] = scanner.nextInt(); map.put(inArr[i], i); } arr = new int[n]; setArr(0, n-1, 0, n-1, n-1); for(int i=0;i<n;i++) { System.out.print(arr[i]+" "); } } static int setArr(int preStart,int preEnd,int inStart,int inEnd,int postIndex) { if(preStart>preEnd) return postIndex; arr[postIndex--] = preArr[preStart]; int index = map.get(preArr[preStart]); postIndex = setArr(index - inStart + preStart +1 , preEnd, index+1,inEnd,postIndex); return setArr(preStart+1,index - inStart + preStart ,inStart,index-1 ,postIndex); } }