import java.util.Scanner; public class Main{ static StringBuilder result = new StringBuilder(); public static String postByPreAndIn(String pre,String in){ if(pre.length() == 0 || in.length() == 0) return null; int mid = -1; for(int i = 0; i < in.length();i++){ if(in.charAt(i) == pre.charAt(0)){ mid = i; break; } } postByPreAndIn(pre.substring(1,mid+1),in.substring(0,mid)); postByPreAndIn(pre.substring(mid+1,pre.length()),in.substring(mid+1,in.length())); result.append(pre.charAt(0)); return result.toString(); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); String pre = sc.next(); String in = sc.next(); System.out.println(postByPreAndIn(pre,in)); } }
#include<iostream> #include<vector> using namespace std; //构建二叉树结点 struct BTreeNode { char data; BTreeNode* left; BTreeNode* right; BTreeNode(char x):data(x),left(NULL),right(NULL){} }; //根据父节点将二叉树分为左右子树 vector<char> m_copy(vector<char> &v, int l, int r) { return vector<char> (v.begin()+l, v.begin()+r); } //根据前序序列和中序序列重建二叉树 BTreeNode* reConstructBTree(vector<char> pre, vector<char> vin) { if(pre.size() == 0 || vin.size() == 0) return NULL; BTreeNode* node = new BTreeNode(pre[0]); for(unsigned long i = 0; i < vin.size(); ++i) { if(pre[0] == vin[i]) { node->left = reConstructBTree(m_copy(pre,1,i+1),m_copy(vin,0,i)); node->right = reConstructBTree(m_copy(pre,i+1,pre.size()),m_copy(vin,i+1,vin.size())); } } return node; } //后序遍历二叉树 void PastOrder(BTreeNode* p) { if(p == NULL) return; PastOrder(p->left); PastOrder(p->right); cout<<p->data; } int main() { string s1,s2; cin>>s1>>s2; if(s1.size()!=s2.size()) { return -1; } int length=s1.size(); vector<char> pre,vin; for(int i=0;i<length;i++) { pre.push_back(s1[i]); vin.push_back(s2[i]); } BTreeNode* res = reConstructBTree(pre, vin); PastOrder(res); return 0; }参考:https://blog.csdn.net/qq_26079093/article/details/102061002
看到很多人都是重建二叉树再后序遍历,其实可以直接算出后序遍历的字符串。
前序:ABDEC
中序:DBEAC
后序:DEBCA
第一轮递归中,我们可以找到规律:
根节点为A,左树节点为DBE,右树节点为C。
从这可以看出后序的结果是左树节点 + 右树节点 + A拼起来的,从而在每次递归里,将A放在最后即可。
完整代码:
var [preOrder, midOrder] = readline().split(/\s+/); function computedPost(pre, mid) { var root = pre[0], strLen = pre.length; if (strLen < 1) { return '' } else if (strLen < 2) { return root; } var m = 0 while (mid[m] !== root) { m++ } return computedPost( pre.slice(1, m + 1), mid.slice(0, m) ) + computedPost( pre.slice(m + 1), mid.slice(m + 1) ) + root } print(computedPost(preOrder, midOrder))
import java.util.*; class TreeNode{ char val; TreeNode left; TreeNode right; TreeNode(char val){ this.val = val; } } public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); char[] pre = sc.next().toCharArray(); char[] in = sc.next().toCharArray(); TreeNode node = build(pre,in); after(node); } public static TreeNode build(char[] pre,char[] in){ if(pre.length==0||in.length==0) return null; TreeNode node = new TreeNode(pre[0]); for(int i =0;i<in.length;i++){ if(in[i]==pre[0]){ node.left=build(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i)); node.right=build(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length)); } } return node; } public static void after(TreeNode node){ if(node == null) return; after(node.left); after(node.right); System.out.print(node.val); } }
#include<iostream> #include<vector> using namespace std; typedef vector<char> VC; int find(VC v, int start, int end, char t){ int i; for(i=start;i<=end;i++) if(v[i]==t) break; return i; } VC reConstruct(VC pre,int l1,int r1,VC vin,int l2, int r2){ VC res; if(l1<=r1){ res.push_back(pre[l1]); int div=find(vin,l2,r2,pre[l1]); VC lv,rv; lv=reConstruct(pre, l1+1, l1+div-l2, vin, l2, div-1); rv=reConstruct(pre, l1+div-l2+1, r1, vin, div+1, r2); res.insert(res.begin(), rv.begin(), rv.end()); res.insert(res.begin(), lv.begin(), lv.end()); } return res; } VC reConstructBinaryTree(VC pre,VC vin) { return reConstruct(pre,0,pre.size()-1,vin,0,vin.size()-1); } int main(){ //NLR LNR LRN string a,b; cin>>a>>b; VC pre(a.length()),in(b.length()); for(int i=0;i<a.length();i++){ pre[i]=a[i]; in[i]=b[i]; } VC r=reConstructBinaryTree(pre,in); for(int i=0;i<r.size();i++) cout<<r[i]; cout<<endl; return 0; }若把vector<char>换成string,会更快一些;
import sys # 定义节点 class TreeNode(object): def __init__(self,val,left=None,right=None): self.val = val self.left = left self.right = right # 重建二叉树 def rebuild(pre,pos): if pre =='': return val = pre[0] index = pos.index(val) root = TreeNode(val) root.left = rebuild(pre[1:1+index],pos[:index]) root.right = rebuild(pre[1+index:],pos[index+1:]) return root # 后续遍历第归实现 def posorder(root): if root is None: return posorder(root.left) posorder(root.right) print(root.val,end='') if __name__ =="__main__": line = sys.stdin.readline().strip() pre,pos = line.split() root = rebuild(pre,pos) res = posorder(root)
#include <iostream> #include <vector> using namespace std; struct TreeNode{ char val; TreeNode* left; TreeNode* right; TreeNode(char x):val(x),left(NULL),right(NULL){} }; TreeNode* Reconstruct(vector<char> pre,vector<char> vin){ int length=pre.size(); if(length==0){ return nullptr; } TreeNode *root=new TreeNode(pre[0]); if(length==1){ if(pre==vin){ return root; } else return nullptr; } int rootInorder=0; while(rootInorder<length&&vin[rootInorder]!=pre[0]){ rootInorder++; } if(rootInorder==length-1&&vin[rootInorder]!=pre[0]){ return nullptr; } vector<char> left_pre,left_vin,right_pre,right_vin; for(int i=0;i<rootInorder;i++){ left_pre.push_back(pre[i+1]); left_vin.push_back(vin[i]); } for(int i=rootInorder+1;i<length;i++){ right_pre.push_back(pre[i]); right_vin.push_back(vin[i]); } root->left=Reconstruct(left_pre,left_vin); root->right=Reconstruct(right_pre,right_vin); return root; } void Back(TreeNode* root,string* s){ if(root!=nullptr){ Back(root->left,s); Back(root->right,s); *s+=root->val; } } int main(){ string s1,s2; cin>>s1>>s2; if(s1.size()!=s2.size()){ return -1; } int length=s1.size(); vector<char> pre,vin; for(int i=0;i<length;i++){ pre.push_back(s1[i]); vin.push_back(s2[i]); } TreeNode* root=Reconstruct(pre,vin); string s; Back(root,&s); cout<<s; return 0; }
class Treenode: def __init__(self,val): self.val = val self.leftchild = None self.rightchild = None def rebuildtree(prorder,inorder): if len(prorder) == 0: return None else: root = Treenode(prorder[0]) k = inorder.index(prorder[0]) root.leftchild = rebuildtree(prorder[1:k+1],inorder[:k]) root.rightchild = rebuildtree(prorder[k+1:],inorder[k+1:]) return root def postorder(root): if root is not None: postorder(root.leftchild) postorder(root.rightchild) a.append(root.val) import sys zz = list(sys.stdin.readline().strip().split()) z1 = list(zz[0]) z2 = list(zz[1]) a = [] root = rebuildtree(z1,z2) postorder(root) print(''.join(a))
#include<stdio.h> int pre[1000],in[1000],lch[10000],rch[10000],n=0; int build(int,int,int,int); void post(int); int main(){ char s1[1000],s2[1000]; //freopen("input.txt","r",stdin); scanf("%s%s",s1,s2); for(int i=0;s1[i]!='\0';i++){ int tmp1=s1[i]-'A'+1,tmp2=s2[i]-'A'+1; pre[n]=tmp1,in[n++]=tmp2; } int root=build(0,n-1,0,n-1); post(root); } int build(int l1,int r1,int l2,int r2){ if(l1>r1) return 0; int root=pre[l1],cnt=0,i; for(i=l2;i<=r2&&in[i]!=root;i++,cnt++); lch[root]=build(l1+1,l1+cnt,l2,i-1); rch[root]=build(l1+cnt+1,r1,i+1,r2); return root; } void post(int root){ if(!root) return; post(lch[root]),post(rch[root]); printf("%c",'A'+root-1); }
#include<iostream>
#include<cstring>
using namespace std;
void findpost(const char*pre,const char*in,char* post,int n){
if(n==0)return;
int i;
for(i=0;;++i){
if(in[i]==pre[0])break;
}
findpost(pre+1,in,post,i);
findpost(pre+i+1,in+i+1,post+i,n-i-1);
post[n-1]=pre[0];
}
int main(){
char pre[1000]="",in[1000]="",post[1000]="";
cin>>pre>>in;
findpost(pre,in,post,strlen(pre));
cout<<post<<endl;
return 0;
}
import java.util.*; class TreeNode{ char val; TreeNode left = null; TreeNode right = null; TreeNode(char val) { this.val = val;} } public class Main{ public static void main(String []args){ Scanner sc = new Scanner(System.in); while (sc.hasNextLine()){ String[] str = sc.nextLine().split(" "); char []pre = str[0].toCharArray(); char []in = str[1].toCharArray(); TreeNode root = reCon(pre, in); find(root); } } public static TreeNode reCon(char[] pre, char[] in){ if (pre.length==0||in.length==0) return null; TreeNode root = new TreeNode(pre[0]); for (int i=0;i<in.length;i++) if (in[i]==pre[0]){ root.left = reCon( Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i)); root.right = reCon( Arrays.copyOfRange(pre,i+1,in.length),Arrays.copyOfRange(in,i+1,in.length)); } return root; } //递归后序遍历方法: public static void find(TreeNode root){ if (root == null) return; find(root.left); find(root.right); System.out.print(root.val); } /* 非递归后序遍历方法: public static void find(TreeNode root){ if (root == null) return; TreeNode pCur = root; TreeNode pLastVisit = null; Stack<TreeNode> stack = new Stack<>(); while (pCur != null){ stack.push(pCur); pCur = pCur.left; } while (!stack.isEmpty()){ pCur = stack.pop(); if (pCur.right == null||pLastVisit == pCur.right){ System.out.print(pCur.val); pLastVisit = pCur; } else { stack.push(pCur); pCur = pCur.right; while(pCur != null){ stack.push(pCur); pCur = pCur.left; } } } } */ }
#include<bits/stdc++.h> using namespace std; string pos(string pre,string vin){ string res=""; if(pre.size()==0)return res; char temp=pre[0]; int tag=0; for(int i=0;i<vin.size();i++){ if(vin[i]==temp){ tag=i; break; } } string preleft(pre.begin()+1,pre.begin()+1+tag); string preright(pre.begin()+1+tag,pre.end()); string vinleft(vin.begin(),vin.begin()+tag); string vinright(vin.begin()+1+tag,vin.end()); res=pos(preleft,vinleft)+pos(preright,vinright)+temp; if(res.size()==pre.size())return res; } int main(){ string pre, vin; cin >> pre >> vin; cout<<pos(pre,vin); return 0; }
#include<stdlib.h> #include<stdio.h> #include<string> #include<iostream> using namespace std; string pre = "", in = ""; //树的ADT typedef struct Tree{ char data; Tree* lchild; Tree* rchild; } T, *Tnode; //后续遍历 void hOrder(T *t) { //注意非空才打印 if(t != NULL) { hOrder(t->lchild); hOrder(t->rchild); cout<<t->data; } } int findRoot(char a, string s) { for(int i = 0; i < s.size(); ++i) if(s[i] == a) return i; return -1; } //依据前序和中序序列建立树 Tnode build(int from, int to) { //不要忘了返回Null不然会bug if(from > to) return NULL; Tnode root = (Tnode)malloc(sizeof(T)); int rootIndex = 0xffff, t = 0; //寻找划分后的子树的根, 即划分序列中在前序序列中下标最小的那个 for(int i = from; i <= to; i++) { //用划分好的中序序列在前序序列中寻找下标 t = findRoot(in[i], pre); rootIndex = rootIndex < t ? rootIndex : t; } //递归建立树 root->data = pre[rootIndex]; //根坐标更新为中序的坐标进行划分 rootIndex = findRoot(root->data, in); root->lchild = build(from, rootIndex-1); root->rchild = build(rootIndex+1, to); return root; } T* buildTree() { Tnode root = (Tnode)malloc(sizeof(T)); root->data = pre[0]; //划分序列得是中序序列根的下标 int rootIndex = findRoot(pre[0], in); root->lchild = build(0, rootIndex-1); root->rchild = build(rootIndex+1, pre.size()-1); return root; } int main(int argc, char* argv[]) { cin>>pre>>in; T* t = buildTree(); hOrder(t); cout<<endl; return 0; }
// 中规中矩的解题思路 import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); char[] pre = s1.toCharArray(); char[] vin = s2.toCharArray(); Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < vin.length; i++) { map.put(vin[i], i); } TreeNode root = process(pre, 0, pre.length, vin, 0, vin.length, map); prePrint(root); } public static TreeNode process(char[] pre, int preBegin, int preEnd, char[] vin, int vinBegin, int vinEnd, Map<Character, Integer> map) { if (preBegin >= preEnd || vinBegin >= vinEnd) { return null; } int index = map.get(pre[preBegin]); TreeNode root = new TreeNode(vin[index]); int count = index - vinBegin; root.left = process(pre, preBegin + 1, preBegin + count + 1, vin, vinBegin, index, map); root.right = process(pre, preBegin + count + 1, preEnd, vin, index + 1, vinEnd, map); return root; } public static void prePrint(TreeNode root) { if (root == null) { return; } prePrint(root.left); prePrint(root.right); System.out.print(root.val); } } class TreeNode { Character val; TreeNode left; TreeNode right; public TreeNode(Character val) { this.val = val; } }
import java.util.*; public class Main { // 二叉树的后序遍历-同样是递归干嘛造树 public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] s = in.nextLine().split(" "); String pre = s[0], mid = s[1]; for (int i = 0; i < mid.length(); i++) { // 存在map中提高效率 map.put(mid.charAt(i), i); } fun(pre, mid, 0, pre.length()-1, 0, mid.length()-1); System.out.println(res); } static Map<Character, Integer> map = new HashMap<>(); static StringBuilder res = new StringBuilder(); // 递归处理-注意后序是左右根递归的时候是根右左 public static void fun(String pre, String mid, int pstart, int pend, int mstart, int mend) { if (pstart <= pend) { int idx = map.get(pre.charAt(pstart)); res.insert(0, pre.charAt(pstart)); fun(pre, mid, pstart + (idx - mstart) + 1, pend, idx + 1, mend); fun(pre, mid, pstart + 1, pstart + (idx - mstart), mstart, idx - 1); } } }
import java.util.Scanner; /** * @Author: coderjjp * @Date: 2020-04-24 17:06 * @Description: 二叉树后序遍历 * @version: 1.0 */ public class Main { private static void getTree(String pre, int preL, int preR, String mid, int midL, int midR) { if (preL>preR) return ; if (preL==preR){ System.out.print(pre.charAt(preL)); return; } for (int i=midL;i<=midR;i++){ if (pre.charAt(preL)==mid.charAt(i)){ getTree(pre,preL+1,i-midL+preL,mid,midL,i-1); getTree(pre,i-midL+preL+1,preR,mid,i+1,midR); } } System.out.print(pre.charAt(preL)); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String pre = sc.next(); String mid = sc.next(); getTree(pre,0,pre.length()-1,mid,0,mid.length()-1); sc.close(); } }建树Java实现:
import java.util.Scanner; /** * @Author: coderjjp * @Date: 2020-04-24 17:06 * @Description: 二叉树后序遍历 * @version: 1.0 */ public class Main { private class TreeNode{ TreeNode left; TreeNode right; char val; public TreeNode(char val) { this.val = val; } } public StringBuilder getLast(char[] pre,char[] mid){ TreeNode root = getTree(pre,0,pre.length-1,mid,0,mid.length-1); StringBuilder sb = new StringBuilder(); lastSort(root,sb); return sb; } private TreeNode getTree(char[] pre, int preL, int preR, char[] mid, int midL, int midR) { if (preL>preR) return null; if (preL==preR) return new TreeNode(pre[preL]); TreeNode root = new TreeNode(pre[preL]); for (int i=midL;i<=midR;i++){ if (pre[preL]==mid[i]){ root.left=getTree(pre,preL+1,i-midL+preL,mid,midL,i-1); root.right=getTree(pre,i-midL+preL+1,preR,mid,i+1,midR); } } return root; } private void lastSort(TreeNode root, StringBuilder sb) { if (root==null) return; lastSort(root.left,sb); lastSort(root.right,sb); sb.append(root.val); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] pre = sc.next().toCharArray(); char[] mid = sc.next().toCharArray(); StringBuilder last = new Main().getLast(pre,mid); System.out.println(last); sc.close(); } }
import java.util.Scanner; import java.util.Stack; public class Main { private static Stack<Character> result = new Stack<>(); /** * * @return */ public static String print(){ if(result == null || result.size()==0) return ""; String str = ""; while (!result.empty()) { str += result.pop(); } return str; } /** * * @param pre * @param mid * @return 返回後序遍歷 */ public static String after(String pre, String mid){ if(pre == null || pre == "" || mid == null || mid == "" || pre.length() != mid.length() || pre.length() == 0 || mid.length() ==0) return ""; char father = pre.charAt(0); Character character = new Character(father); result.push(character); int dex = 0; while (dex<pre.length() && father != mid.charAt(dex++)); dex--; if(dex + 1 < pre.length()) after(pre.substring(dex + 1, pre.length()), mid.substring(dex + 1, mid.length())); if(dex != 0) after(pre.substring(1, dex+1), mid.substring(0, dex)); return ""; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String pre = in.next(); String mid = in.next(); //System.out.println(pre + " " + mid); after(pre,mid); System.out.println(print()); } }
题目思路挺清晰的,我是先通过前序和中序构造出树结构,再通过递归遍历后序。
在构造二叉树的时候,用哈希表寻找中序遍历中的根节点个很方便。代码如下:
#include <bits/stdc++.h> using namespace std; struct TreeNode{ char val; TreeNode *left; TreeNode *right; TreeNode(char ch) : val(ch), left(NULL), right(NULL) {} }; unordered_map<char, int> h; TreeNode* dfs(vector<char> &preorder, vector<char> &inorder, int pl, int pr, int il, int ir) { if(pl > pr) return NULL; int gen = preorder[pl]; int pos = h[gen]; int len = pos - il; auto root = new TreeNode(gen); root->left = dfs(preorder, inorder, pl + 1, pl + len, il, pos - 1); root->right = dfs(preorder, inorder, pl + len + 1, pr, pos + 1, ir); return root; } TreeNode* Construct(vector<char>& preorder, vector<char>& inorder) { int n = inorder.size(); if(n <= 0) return NULL; for(int i = 0; i < n; i++) h[inorder[i]] = i; return dfs(preorder, inorder, 0, n - 1, 0, n - 1); } void postSearch(TreeNode* root, vector<char> &postorder) { // if(!root) return ; if(root->left) postSearch(root->left, postorder); if(root->right) postSearch(root->right, postorder); postorder.push_back(root->val); } int main() { string a, b; cin >> a >>b; int n = a.size(); vector<char> preorder, inorder, postorder; for(int i = 0; i < n; i++) { preorder.push_back(a[i]); inorder.push_back(b[i]); } TreeNode *root = Construct(preorder, inorder); postSearch(root, postorder); for(int i = 0; i < n; i++) cout << postorder[i]; return 0; }