Tree Traversals (25)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 1020. Tree Traversals (25)
 * 
 * @author Jacob
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] postorder = new int[n];
        int[] inorder = new int[n];
        for (int i = 0; i < n; i++)
            postorder[i] = sc.nextInt();
        for (int i = 0; i < n; i++)
            inorder[i] = sc.nextInt();

        Node root = rebuild(postorder, 0, n - 1, inorder, 0, n - 1);
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        ArrayList<Integer> res = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            res.add(node.value);
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        System.out.print(res.get(0));
        for (int i = 1; i < res.size(); i++) {
            System.out.print(" " + res.get(i));
        }
        sc.close();

    }

    private static Node rebuild(int[] postorder, int postLeft, int postRight, int[] inorder, int inLeft, int inRight) {
//        System.out.println("hhhhhhhhhhh:"+postLeft+" "+postRight+" "+inLeft+" "+inRight);
        if (postLeft > postRight)
            return null;
        Node root = new Node(postorder[postRight]);
        int index = 0;
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == postorder[postRight])
                index = i;
        }
        int leftNum = index - inLeft;

        root.left = rebuild(postorder, postLeft, postLeft + leftNum - 1, inorder, inLeft, index - 1);
        root.right = rebuild(postorder, postLeft + leftNum, postRight - 1, inorder, index + 1, inRight);
        return root;
    }

    /*
     * 构造树节点类
     */
    static class Node {
        public Node(int value) {
            this.value = value;
        }

        int value;
        Node left;
        Node right;
    }
}

	

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define maxn 35
struct node{                                                     //定义树的结点（静态实现）
    int data,lchild,rchild;
}Node[maxn];
int post[maxn],in[maxn],n,num=0;
int create(int inL,int inR,int postL,int postR){
    if(postL>postR) return -1;                                   //若后序序列长度小于等于0
    int root=num++;
    Node[root].data=post[postR];                                 //后序最后一个结点即为根结点
    int mid;
    for(mid=inL;mid<=inR;mid++){                                 //在中序中找到根结点
        if(in[mid]==post[postR]) break;
    }
    Node[root].lchild=create(inL,mid-1,postL,postL+(mid-inL)-1); //返回右子树根结点地址（数组下标）
    Node[root].rchild=create(mid+1,inR,postL+(mid-inL),postR-1);
    return root;
}
void layerOrder(int root){                                       //层次遍历
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        cout<<Node[now].data;
        if(Node[now].lchild!=-1) q.push(Node[now].lchild);
        if(Node[now].rchild!=-1) q.push(Node[now].rchild);
        if(!q.empty()) cout<<" ";
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>post[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    int root=create(0,n-1,0,n-1);                               //构建二叉树并返回根结点地址
    layerOrder(root);
    return 0;
} 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 30;
int in_order[maxn], post_order[maxn];
int n, root, lch[maxn], rch[maxn];	//n为树的结点个数
vector<int> level;

void read_list(int *a){
	int x;
	for(int i=0;i<n;i++){
		cin >> x;
		a[i] = x;
	}
}

//把in_order[L1 ... R1] 和 post_order[L2 ... R2] 建成一棵二叉树
int build(int L1, int R1, int L2, int R2){
	if(L1 > R1) return  0;
	int proot = post_order[R2], pos;
	for(int i=0;i<n;i++){
		if(in_order[i] == proot){
			pos = i;
			break;
		}
	}
	int l_num = pos - L1; //左子树的结点个数
	lch[proot] = build(L1, pos-1, L2, L2+l_num-1);
	rch[proot] = build(pos+1, R1, L2+l_num, R2-1);
	return proot;
}

void level_order(int proot){
	queue<int> q;
	q.push(proot);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		level.push_back(u);
		if(lch[u]) q.push(lch[u]);
		if(rch[u]) q.push(rch[u]);
	}
}

int main(){
	cin >> n;
	memset(lch, 0, sizeof(lch));
	memset(rch, 0, sizeof(rch));
	read_list(post_order);
	read_list(in_order);
	build(0, n-1, 0, n-1);
	level_order(post_order[n-1]);
	cout << level[0];
	for(unsigned int i=1;i<level.size();i++)
		cout << " " << level[i];
	return 0;
}

算是比较典型吧

#include<cstdio>
#include<queue>
using namespace std;
struct Node {
    int data;
    Node *l;
    Node *r;
};
int p[31], i[31],c[31],cnt=0;
Node *root;
queue<Node*> q;
Node* create(int pl, int pr, int il, int ir) {
    if (pl > pr || il > ir) {
        return NULL;
    }
    Node* root = new Node;
    root->data = p[pr];
    int k;
    for (k = il;k<=ir; k++) {
        if (i[k] == p[pr])
            break;
    }
    int nl = k - il;
    root->l = create(pl, pl + nl - 1, il, k - 1);
    root->r = create(pl + nl, pr - 1, k + 1, ir);
    return root;
}
void BFS(Node *n) {
    q.push(n);
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        c[cnt++] = temp->data;
        if (temp->l != NULL)
            q.push(temp->l);
        if (temp->r != NULL)
            q.push(temp->r);
    }
}
int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &p[i]);
    }
    for (int j = 1; j <= N; j++) {
        scanf("%d", &i[j]);
    }
    root=create(1,N,1,N);
    BFS(root);
    for (int i = 0; i < N; i++) {
        printf("%d", c[i]);
        if (i < N - 1)
            printf(" ");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

struct node {
	int data;
	node* lchild;
	node* rchild;
	node(int a):data(a),lchild(NULL),rchild(NULL) {
	}
};

const int Max=50;
int n,P[Max],I[Max];

node* create(int p1,int p2,int i1,int i2) {
	if(p1>p2) {
		return NULL;
	}
	node* root=new node(P[p2]);
	int k;
	for(k=i1; k<=i2; k++) {
		if(I[k]==P[p2]) {
			break;
		}
	}
	int num=k-i1;
	root->lchild=create(p1,p1+num-1,i1,k-1);
	root->rchild=create(p1+num,p2-1,k+1,i2);
	return root;
}

int num=0;
void BFS(node* root) {
	queue<node*> q;
	q.push(root);
	while(!q.empty()) {
		node* now=q.front();
		q.pop();
		cout<<now->data;
		num++;
		if(num<n) cout<<" ";
		if(now->lchild!=NULL) {
			q.push(now->lchild);
		}
		if(now->rchild!=NULL) {
			q.push(now->rchild);
		}
	}
}

int main() {
	while(cin>>n) {
		for(int i=0; i<n; i++) {
			cin>>P[i];
		}
		for(int i=0; i<n; i++) {
			cin>>I[i];
		}
		node* root=create(0,n-1,0,n-1);
		BFS(root);
	}
	return 0;
}

思路：不构建二叉树，使用队列+下标逐级分解二叉树
1、后序遍历最后一节点为根节点
2、中序二叉树中根节点的位置可以确定左右子树的中序遍历 和 对应的节点数
3、根据节点数，可以在后序遍历中得到左右子树的后序遍历

#include<iostream>
using namespace std;

int main()
{
    int n, post[35], in[35], i;
    int s1[35], e1[35], s2[35], e2[35], front, end;
    cin >> n;
    for (i = 0; i < n; ++i)
        cin >> post[i];
    for (i = 0; i < n; ++i)
        cin >> in[i];
    front = -1, end = 0;
    s1[end] = s2[end] = 0;
    e1[end] = e2[end] = n-1;
    while(end != front)
    {
        if (front != -1)
            cout << " ";
        cout << post[e1[++front]];
        for (i = s2[front]; i <= e2[front]; ++i)
            if (in[i] == post[e1[front]])
                break;
        if (s1[front] != e1[front])
        {
            if (i > s2[front])
            {
                s1[++end] = s1[front];
                e1[end] = s1[front]+i-s2[front]-1;
                s2[end] = s2[front];
                e2[end] = i-1;
            }
            if (i < e2[front])
            {
                s1[++end] = s1[front]+i-s2[front];
                e1[end] = e1[front]-1;
                s2[end] = i+1;
                e2[end] = e2[front];
            }
        } 
    }
    return 0;
}

#include<iostream>
(720)#include<cstdio>
#include<stack>
(850)#include<queue>
using namespace std;
struct node{
	int data;
	node* left;
	node* right;
	node(int x):data(x),left(NULL),right(NULL){}
};
int pre[35];
int in[35];
int post[35];

node* create(int postl,int postr,int inl,int inr){
	if(postl>postr){
		return NULL;
	}
	node* root=new node(post[postr]);
	int i;
	for(i=inl;i<=inr;i++){
		if(in[i]==post[postr])
		break;
	}
	root->left=create(postl,postl+i-inl-1,inl,i-1);
	root->right=create(postl+i-inl,postr-1,i+1,inr);
//	cout<<"complete!!!"<<endl;
	return root;
}
void BFS(node* root){
	queue<node*> res;
	res.push(root);
	while(!res.empty()){
		node* cur=res.front();
		int temp=cur->data;
		cout<<temp<<" ";
		res.pop();
		if(cur->left){
			res.push(cur->left);
		}
		if(cur->right){
			res.push(cur->right);
		}
	}
}

int main(){
	int count;
	cin>>count;
	for(int i=0;i<count;i++){
		cin>>post[i];
	}
	for(int i=0;i<count;i++){
		cin>>in[i];
	}
	node* root=create(0,count-1,0,count-1);
	BFS(root);
	return 0;    
}//幼儿园级别的代码水平，参考了算法笔记

input()
d,m,p = {},[],0
a,d[0] = input().split()[::-1],[input().split()[::-1]]
try:
    while a:
        for i in range(len(d[p])):
            if len(d[p][i]) <= 1:continue
            for j in a:
                if j in d[p][i]:
                    a.remove(j)
                    break
            for k in range(len(d[p][i])):
                if d[p][i][k] == j:
                    break
            try:
                d[p + 1].extend([d[p][i][:k],d[p][i][1 + k:]])
            except:
                d[p + 1] = [d[p][i][:k],d[p][i][1 + k:]]
            d[p][i] = [j]
        p += 1
except:
    for i in d:
        try:
            while True:
                d[i].remove([])
        except:
            pass

for i in d:
    for j in d[i][::-1]:
        m += [j[0]]
print(' '.join(' '.join(m).split()))

#define _CRT_SECURE_NO_WARNINGS  
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<string>
#include<map>
#include<queue>
using namespace std;

int n=0;
vector<int> post;
vector<int> in;

struct node
{
    int num;
    struct node *left=NULL;
    struct node *right=NULL;
    node(int num = 0, struct node *left = NULL, struct node *right = NULL) {
        this->num = num;
        this->left = left;
        this->right = right;
    }
};

int findpos(int a) {
    for (int i = 0; i < n; i++) {
        if (in[i] == a) {
            return i;
        }
    }
    return 0;
}

struct node *buildtree(int lowpost, int highpost, int lowin, int highin)
{
    //int pos = findpos(post[highpost]);
    ////cout << lowpost << ' ' << highpost << ' ' << lowin << ' ' << highin <<' '<<pos<< endl;
    ////getchar();
    //struct node newnode = {0,NULL,NULL};

    //newnode.num = post[highpost];
    ////cout << newnode.num << endl;
    //if (lowin <= pos - 1) {
    //    newnode.left = buildtree(lowpost, lowpost + pos - lowin-1, lowin, pos - 1);
    //}
    //if (pos + 1 <= highin) {
    //    newnode.right = buildtree(highpost - 1 - (highin - pos-1), highpost - 1, pos + 1, highin);
    //}
    //cout << (int)&newnode << endl;
    //cout << newnode.num<<endl;
    //return &newnode;

    int pos = findpos(post[highpost]);
    //cout << lowpost << ' ' << highpost << ' ' << lowin << ' ' << highin <<' '<<pos<< endl;
    //getchar();
    struct node *newnode =new struct node;
    newnode->num = post[highpost];
    //cout << newnode.num << endl;
    if (lowin <= pos - 1) {
        newnode->left = buildtree(lowpost, lowpost + pos - lowin - 1, lowin, pos - 1);
    }
    if (pos + 1 <= highin) {
        newnode->right = buildtree(highpost - 1 - (highin - pos - 1), highpost - 1, pos + 1, highin);
    }
    //cout << (int)newnode << endl;
    //cout << newnode->num << endl;
    return newnode;
}


int main()
{
    freopen("data.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        post.push_back(a);
    }
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        in.push_back(a);
    }
    freopen("CON", "r", stdin);

    struct node * root;
    //节点数一定大于零
    root=buildtree(0, n - 1, 0, n - 1);//该子树后续开始结束，中序开始结束，返回建立好的子树的根指针
    //cout << (int)root << endl;
    //cout << root->num << endl;
    //cout << (int)root->left << endl;



    //层序遍历打印
    queue<struct node*> q;
    q.push(root);
    bool isfirst = true;
    while (q.empty() != true) {
        if (isfirst == true) {
            printf("%d", q.front()->num);
            isfirst = false;
        }
        else {
            printf(" %d", q.front()->num);
        }
        if (q.front()->left != NULL) {
            q.push(q.front()->left);
        }
        if (q.front()->right != NULL) {
            q.push(q.front()->right);
        }
        q.pop();
    }


    
    getchar();
    return 0;
}


问一下buildtree注释部分的新节点声明有什么问题呢? 
buildtree中使用new来初始化节点是可以的，直接调用构造函数却不对

class TreeNode(object):
    def __init__(self, data=0, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def parseTree(po, ino, n):
    if n == 0:
        return None
    idx = ino.index(po[n-1])
    root = TreeNode(po[n-1])
    root.left = parseTree(po[:idx], ino[:idx], idx)
    root.right = parseTree(po[idx:n-1], ino[idx+1:], n-idx-1)
    return root

def levelTraverse(root):
    queue = []; rlt = []
    queue.append(root)
    while queue:
        node = queue.pop(0)
        rlt.append(node.data)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return rlt
N = input()
po = map(int, raw_input().strip().split())
ino = map(int, raw_input().strip().split())
root = parseTree(po, ino, N)
rlt = levelTraverse(root)
rlt = map(str, rlt)
print(' '.join(rlt))