首页 > 试题广场 >

Tree Traversals Again (25)

[编程题]Tree Traversals Again (25)
  • 热度指数：3946 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1

输入描述:
Each input file contains one test case.  For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N).  Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.


输出描述:
For each test case, print the postorder traversal sequence of the corresponding tree in one line.  A solution is guaranteed to exist.  All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
示例1

输入

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

输出

3 4 2 6 5 1
算法知识视频讲解
添加回答
SchizoidDragon头像 SchizoidDragon
二叉树中序遍历的非递归实现需要利用一个栈，现在给出这个栈的 Push、 Pop 操作序列，求这棵树的后序遍历序列。

中序遍历序列可以模拟栈操作获得，另外注意所有 Push 的节点组成的序列就是这棵树的先序遍历序列。于是问题转为从一棵树的先序遍历序列和中序遍历序列生成这棵树。

下面的代码在 www.patest.cn 提交可以通过，但是在这里直接运行错误了，不清楚是什么原因。 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <limits.h>

using namespace std;

// 树节点定义
struct TreeNode
{
    TreeNode(int v) : val(v)
    {
        left = NULL;
        right = NULL;
    }

    int val;
    TreeNode *left, *right;
};

// 从先序遍历序列和中序遍历序列中构建一棵树
TreeNode* create_tree(
    const vector<int> &pre_order, int pre_start, int pre_end, 
    const vector<int> &in_order, int in_start, int in_end,
    const map<int, int> &h_inorder_pos)
{
    if (pre_start >= pre_end || in_start >= in_end)
        return NULL;
    
    int root_val = pre_order[pre_start];
    int root_inorder_pos = h_inorder_pos.at(root_val);
    int left_size = root_inorder_pos - in_start;

    TreeNode *root = new TreeNode(root_val);
    root->left = create_tree(
        pre_order, pre_start + 1, pre_start + left_size + 1, 
        in_order, in_start, root_inorder_pos, h_inorder_pos);
    root->right = create_tree(
        pre_order, pre_start + left_size + 1, pre_end, 
        in_order, root_inorder_pos + 1, in_end, h_inorder_pos);

    return root;
}

// 二叉树后序遍历，pred 为对节点的访问方法
void post_order_traverse(TreeNode *root, vector<int> &post_order)
{
    if (!root)
        return;

    post_order_traverse(root->left, post_order);
    post_order_traverse(root->right, post_order);
    post_order.push_back(root->val);
}

void destroy_tree(TreeNode *root)
{
    if (!root)
        return;
    destroy_tree(root->left);
    destroy_tree(root->right);

    delete root;
    root = NULL;
}

int main(int argc, char * const argv[])
{
    int n;
    cin >> n;

    vector<int> pre_order;
    vector<int> in_order;
    stack<int> s;

    int x;
    string operation;

    while (cin >> operation)
    {
        if (operation == "Push")
        {
            cin >> x;
            pre_order.push_back(x);  // 将每次 Push 的节点保存到先序遍历序列
            s.push(x);
        }
        else  // Pop
        {
            in_order.push_back(s.top());  // 保存到中序遍历序列
            s.pop();
        }
    }

    // 用 Hash 表保存每个节点在中序遍历序列中的位置
    map<int, int> h_inorder_pos;
    for (int i = 0; i < in_order.size(); ++i)
    {
        h_inorder_pos[in_order[i]] = i;
    }

    // 构建树
    TreeNode *tree = create_tree(pre_order, 0, pre_order.size(), in_order, 0, in_order.size(), h_inorder_pos);

    vector<int> post_order;  // 后序遍历序列

    // 生成后序遍历序列
    post_order_traverse(tree, post_order);

    // 后序遍历删除树
    destroy_tree(tree);

    // 输出后序遍历序列
    for (int i = 0; i < post_order.size(); ++i)
    {
        cout << (i == 0 ? "" : " ") << post_order[i];
    }
    cout << endl;

    return 0;
}
 



发表于 2015-11-04 22:02:51 回复(3)
更多回答
推荐
orgcheng头像 orgcheng
解题思路
step one: 首先根据输入，构造出原树的结构。
step two: 后序遍历原树。

关于第一步，需要观察Push和Pop，找出构造原树的方法：
每次Push相当于插入节点，Pop相当于回朔，为了便于回朔的实现，根据最后Pop出的节点的 Id，从已经构造的原树中查找应该回朔到的节点。

关于第二步，如果有n个节点，需要输出n-1个空格，经过观察发现，打印每个节点时，后面跟一个空格，根节点除外，这样就可以打印符合要求的结果，所以只需要能判断是否为根节点即可。

代码如下：
import java.io.PrintStream;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	// 树的定义
	public class Tree{
		int node;
		int id;
		Tree left;
		Tree right;
		public Tree(int id, int node){
			this.id = id;
			this.node = node;
			left = right = null;
		}
	}
	public void treeTraveral(){
		Tree root = recoverTree();
		
		// 后序打印树
		if(root!=null){
			postPrintTree(root, root.id);
		}
	}
	public Tree recoverTree(){
		Stack<Integer> stack = new Stack<>();
		Tree root = null,treeIndex=null;
		int n = Integer.valueOf(in.nextLine());
		
		Integer val,popId=null;
		
		int id = 1;
		// 构造树的结构
		for(int i=0;i<2*n;++i){
			String line = in.nextLine();
			if(line.startsWith("Push")){
				val = Integer.valueOf(line.substring(5));
				stack.push(id);
				
				if(root == null){
					root = new Tree(id++,val);
					treeIndex = root;
				}else{
					if(popId!=null){
						treeIndex = getNodeFromValue(root, popId);
					}
					Tree tmp = new Tree(id++,val);
					if(treeIndex.left == null){
						treeIndex.left = tmp;
					}else{
						treeIndex.right = tmp;
					}
					treeIndex = tmp;
				}
				
				popId=null;
				
			}else{
				popId = stack.pop();
			}
		}
		
		return root;
	}
	/*
	 * 根据节点值，获取树中该节点的引用
	 * 注意：节点值唯一
	 */
	public Tree getNodeFromValue(Tree root, int id){
		// 边界
		if(root == null)
			return null;
		if(root.id == id )
			return root;
		//递归搜索左子树
		Tree result = getNodeFromValue(root.left, id);
		
		//递归搜索右子树
		if(result==null){
			result = getNodeFromValue(root.right, id);
		}
		return result;
	}
	
	/*
	 * 后序打印树中的节点值 
	 */
	public void postPrintTree(Tree root, int rootId){
		if(root==null)
			return;
		
		if(root.left == null && root.right == null){
			out.print(root.node);
			if(root.id!=rootId){
				out.print(" ");
			}
			return;
		}
		// 递归打印左子树
		if(root.left!=null){
			postPrintTree(root.left,rootId);
		}
		// 递归打印右子树
		if(root.right!=null){
			postPrintTree(root.right,rootId);
		}
		
		// 打印父节点
		out.print(root.node);
		if(root.id!=rootId){
			out.print(" ");
		}
	}
	
	public static Scanner in = new Scanner(System.in);
	public static PrintStream out = System.out;
	
	public static void main(String[] args) {
		Main t = new Main();
		t.treeTraveral();
	}
}

编辑于 2015-08-18 21:33:18 回复(0)
元气の悟空头像 元气の悟空 
//AC代码：
#include<stdio.h>
int lch[100],rch[100],
pre[100],inorder[100],sum=0,v[100];
int build(int,int,int,int);
void postOrder(int,int);
int main(){
    //freopen("input.txt","r",stdin);
    int n,i,x,c1=0,c2=0,stack[100],c=-1;
    for(scanf("%d",&n),i=0;i<2*n;i++){
        char in[100];
        scanf("%s",in);
        if(in[1]=='u') 
            scanf("%d",&x),
            pre[c1]=c1+1,stack[++c]=++c1,v[c1]=x;
        else inorder[c2++]=stack[c--];
    }
    int root=build(0,c1-1,0,c2-1);
    postOrder(root,n);
}
int build(int l1,int r1,int l2,int r2){
    if(l1>r1) return 0;
    int root=pre[l1],i,cnt=0;
    for(i=l2;inorder[i]!=root;cnt++,i++);
    lch[root]=build(l1+1,l1+cnt,l2,i-1);
    rch[root]=build(l1+cnt+1,r1,i+1,r2);
    return root;
}
void postOrder(int x,int n){
    if(!x) return;
    postOrder(lch[x],n);
    postOrder(rch[x],n);
    printf("%d",v[x]),sum++;
    if(sum-n) printf(" ");
    else printf("\n");
}

发表于 2017-10-29 12:31:35 回复(0)
ZilSPK头像 ZilSPK
这个题好坑啊.....没分辨出来序号和键值，提交后段错误+答案正确+答案错误简直让人抓狂.... 
Push 1   //结点编号为1 键值为1
Push 2   //结点编号为2 键值为2
Push 3   
Pop      //编号为3的结点被中序遍历到
Pop      
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
后续遍历的时候输出的不是编号，而是结点的键值
@啥 提供的测试样例：

19
Push 4     //结点编号为1  键值为4
Push 11  
Push 7
Push 12
Pop
Pop
Pop
Push 14
Push 17
Pop
Pop
Push 6
Push 18
Pop
Push 8
Pop
Pop
Push 4
Pop
Pop
Push 11
Push 16
Push 11
Push 12
Pop
Push 2
Pop
Pop
Pop
Push 7
Push 4
Pop
Pop
Push 12
Pop
Pop
Push 11
Pop

发表于 2019-01-30 12:35:44 回复(0)
C/C++
RicardoZi头像 RicardoZi 
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;

const int maxn = 60;
int cnt=0, root=0, n, lch[maxn], rch[maxn];
bool flag = true;

void build(int lroot, int *a){
	if(cnt > 2*n-1) return;
	string s;
	cin >> s;
	if(s[1] == 'o') {
		cnt ++;
		return;
	}
	if(s[1] == 'u'){
		int num;
		cnt ++;
		cin >> num;
		a[lroot] = num;
		build(num, lch);
		build(num, rch);
	}
}

void init(){
	string s;
	cin >> s;
	if(s[1] == 'o') {
		cnt ++;
		return;
	}
	if(s[1] == 'u'){
		cnt ++;
		cin >> root;
		build(root, lch);
		build(root, rch);		
	}
}

void post_order(int proot){
	if(proot == 0) return;
	post_order(lch[proot]);
	post_order(rch[proot]);
	if(flag) printf("%d", proot);
	else printf(" %d", proot);
	flag = false;
}

int main(){
	memset(lch, 0, maxn);
	memset(rch, 0, maxn);
	scanf("%d", &n);
	
	init();
	if(root) post_order(root);
	cout << endl;
	return 0;
}
数组实现树，代码较为简单！
发表于 2017-07-27 17:02:42 回复(1)
在最美的年华头像 在最美的年华
内存超限怎么破呀。。。。？
发表于 2018-11-10 22:15:52 回复(1)
啥头像 啥
总体思路：
        1.根据前序和中序重建二叉树。  push部分相当于前序，pop部分相当于中序
        2.把二叉树后序输出
注意点：
        1.要把节点的  标号  和  值  区分开来。  根据标号的前序中序重建二叉树，而不是值
        2.从1到N是说标号的，不是说值
一个测试用例：
19
Push 4
Push 11
Push 7
Push 12
Pop
Pop
Pop
Push 14
Push 17
Pop
Pop
Push 6
Push 18
Pop
Push 8
Pop
Pop
Push 4
Pop
Pop
Push 11
Push 16
Push 11
Push 12
Pop
Push 2
Pop
Pop
Pop
Push 7
Push 4
Pop
Pop
Push 12
Pop
Pop
Push 11
Pop

对应输出应该为:
12 7 17 8 18 4 6 14 11 2 12 11 4 12 7 16 11 11 4

python代码： 
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class BinaryTree:
    def __init__(self, root=None):
        self.root = root
    def postOrder(self, tree):
        if tree is not None:
            self.postOrder(tree.lchild)
            self.postOrder(tree.rchild)
            self.visit(tree)
    def visit(self, tree):
        print data[tree.data],

def constructBinaryTree(pre, s1, e1, inOrder, s2, e2):
    if s1 > e1:
        return None
    idx = inOrder.index(pre[s1])
    root = TreeNode(pre[s1])
    root.lchild = constructBinaryTree(pre, s1+1, s1+idx-s2, inOrder, s2, idx-1)
    root.rchild = constructBinaryTree(pre, s1+idx-s2+1, e1, inOrder, idx+1, e2)
    return root

data = []; idx = []; num = 0
preOrder = []; inOrder = []
N = int(raw_input())
for i in range(N*2):
    line = raw_input().strip().split()
    if line[0] == 'Push':
        data.append(int(line[1]))
        preOrder.append(num)
        idx.append(num)
        num += 1
    else:
        inOrder.append(idx.pop())
bt = BinaryTree(constructBinaryTree(preOrder, 0, N-1, inOrder, 0, N-1))
bt.postOrder(bt.root)


发表于 2016-01-23 15:34:24 回复(2)
专属回忆』头像 专属回忆』 
#include <iostream>
 #include <vector>
 using namespace std;
 struct node {
  int v;
  node *left, *right, *par;
  bool pop;
  node(int val):v(val) {
   left = NULL;
   right = NULL;
   par = NULL;
   pop = false;
  }
 };
 int n, inNum;
 string inOp;
 vector<int> postVec;  // 存储后序遍历的序列 
 void postTravel(node *root) {
  if(root == NULL)
   return;
  postTravel(root->left);
  postTravel(root->right);
  postVec.push_back(root->v);
 }
 void destoryTree(node *root) {
  if(!root)
   return;
  destoryTree(root->left);
  destoryTree(root->right);
  delete root;
  root = NULL; 
 }
 int main() {
  cin >> n;
  node *root = NULL;
  node *cur = NULL;
  for(int i=1; i <= 2*n; ++i) {
   cin >> inOp;
   if(inOp.at(inOp.length()-1) == 'h') { // Push
    cin >> inNum;
    node *n = new node(inNum);
    if(cur == NULL) {
     root = n;
     cur = root;
    } else {
     if(cur->left == NULL)
      cur->left = n;
     else
      cur->right = n;
     n->par = cur;
     cur = n;
    }
   } else {     // Pop
    while(cur->pop)
     cur = cur->par;
    cur->pop = true;
   }
  }
  postTravel(root);
  for(int i=0; i<postVec.size(); ++i)
   cout << (i==0 ? "" : " ") << postVec[i];  //注意输出格式 
  cout << endl;
  destoryTree(root);
  return 0;
 }

发表于 2017-11-05 19:52:44 回复(0)
汤圆坨头像 汤圆坨 
#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>

using namespace std;

bool isFirst = true;

typedef struct BinaryTree {
	int data;
	BinaryTree* left;
	BinaryTree* right;
} BiTree;

void postOrderTravel(BiTree* tree) {
	if (tree != NULL) {
		postOrderTravel(tree->left);
		postOrderTravel(tree->right);
		if(isFirst) {
            cout << tree->data;
            isFirst = false;
		} else {
            cout << " " << tree->data;
		}
	}
}

int main() {
	BiTree *root, *index, *parrent;
	int lr = 0;
	root = (BiTree*)malloc(sizeof(BiTree));
	root->right = NULL;
	root->left = NULL;
	index = root;
	parrent = root;
	stack<BiTree*> BiStack;
	int count;
	cin >> count;
	int i = 0;
	while (i < count || !BiStack.empty()) {
		string order;
		cin >> order;
		if (order == "Push") {
			int data;
			cin >> data;
			i++;
			index->data = data;
			BiStack.push(index);
			index->left = (BiTree*)malloc(sizeof(BiTree));
			parrent = index;
			lr = 0;
			index = index->left;
			index->right = NULL;
			index->left = NULL;
		}
		else if (order == "Pop") {
			free(index);
			if (lr == 0) {
				parrent->left = NULL;
			}
			else if (lr == 1) {
				parrent->right = NULL;
			}
			BiTree* top = BiStack.top();
			BiStack.pop();
			if (i == count && BiStack.empty()) {
				break;
			}
			top->right = (BiTree*)malloc(sizeof(BiTree));
			parrent = top;
			lr = 1;
			index = top->right;
			index->right = NULL;
			index->left = NULL;

		}
	}

	postOrderTravel(root);
	return 0;
}

发表于 2020-09-13 10:55:25 回复(0)
桐棯头像 桐棯 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String index = "left";//记录当前是在左孩子节点处插入，还是在右孩子节点处插入
        Node root = null;
        Deque<Node> deque = new ArrayDeque<>();
        //构造出原树的结构。
        for (int i = 0; i < n * 2; i++) {
            String command = sc.next();
            if (command.equals("Push")) {
                int val = sc.nextInt();
                Node node = new Node(val);
                if (deque.isEmpty()) {//如果栈为空，记录根结点
                    root = node;
                    deque.push(node);
                } else {
                    if (index.equals("left")) {
                        deque.peek().left = node;
                    } else {
                        deque.peek().right = node;
                        deque.pop();//如果是插入右孩子结点，这将去除当前栈顶处的结点
                        index = "left";
                    }
                    deque.push(node);
                }
            } else {//command="Pop"
                if (index.equals("left")) {
                    index = "right";
                } else {
                    deque.pop();
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        //后序遍历原树。
        postorder(root, ans);
        for (int i = 0; i < ans.size(); i++) {
            if(i!=ans.size()-1)
                System.out.print(ans.get(i)+" ");
            else
                System.out.print(ans.get(i));
        }
    }

    static void postorder(Node node, List<Integer> ans) {
        if (node == null) return;
        postorder(node.left, ans);
        postorder(node.right, ans);
        ans.add(node.val);
    }
}

class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
        this.val = val;
    }
}

发表于 2022-11-14 15:04:27 回复(0)
夜语声烦-头像 夜语声烦-

PAT能过，牛客过不了，服了

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

const int N = 40;

int n, pos[N];
stack<int> stk;
vector<int> pre, in, post;
int l[N], r[N];

int build(int il, int ir, int pl, int pr)
{
    int root = pre[pl];        
    int k = pos[root];
    if (il < k) l[root] = build(il, k - 1, pl + 1, pl + k - il);
    if (ir > k) r[root] = build(k + 1, ir, pr - ir + k + 1, pr);
    return root;
}

void postorder(int root)
{
    if (l[root]) postorder(l[root]);
    if (r[root]) postorder(r[root]);
    post.push_back(root);
}

int main()
{
    cin >> n;
    for (int i = 0; i < 2 * n; i ++)
    {
        string op; int t;
        cin >> op;

        if (op == "Push")
        {
            cin >> t;
            stk.push(t);
            pre.push_back(t);
        }
        else
        {
            in.push_back(stk.top());
            stk.pop();
        }
    }

    for (int i = 0; i < n; i ++) pos[in[i]] = i;
    int root = build(0, n - 1, 0, n - 1);
    postorder(root);

    cout << post[0];
    for (int i = 1; i < n; i ++) cout << ' ' << post[i];

    return 0;
}
发表于 2022-10-18 22:55:25 回复(0)
C/C++
想去毕业旅行的猴子在泡池子头像 想去毕业旅行的猴子在泡池子
简单易懂  
这道题坑我好长时间   测试点好多都有重复的值 不利于找出根节点在中序遍历中的位置 

#include<stack>
#include <iostream>
#include<stdio.h>
using namespace std;
int N,pcount=0,icount=0;
//设置uniquepre和uniquein是因为   节点的value值不唯一
int pre[40], in[40], uniquepre[40], uniquein[40];
stack<int>s,b;
struct node {
    int value;
    node* left;
    node* right;
};
int flag = 1;
//后续遍历二叉树,先左后右再根
void postorder(int h1,int t1,int h2,int t2)
{
    //先在中序遍历序列中找出根节点的位置
    int mid = h2;
    for (; uniquein[mid] != uniquepre[h1]; mid++);
    //遍历左子树
    if(mid>h2)
        postorder(h1 + 1, mid + h1 - h2, h2, mid - 1);
    if(mid<t2)
        postorder(t1 - t2 + mid + 1, t1, mid + 1, t2);
    if (flag)
    {
        cout << pre[h1];
        flag = 0;
    }
    else
        cout << ' ' << pre[h1];
}
int main()
{
    cin >> N;
    int a,len = 2 * N;
    char temp[10];
    //从输入数据中提取出先序遍历和中序遍历序列
    for (int i = 0; i < len; i++)
    {
        scanf("%s", temp);
        if (temp[1] == 'u')//Push操作
        {
            scanf("%d", &a);
            uniquepre[pcount] = pcount;
            b.push(pcount);
            pre[pcount++] = a;
            s.push(a);
            continue;
        }
        else if (temp[1] == 'o')
        {
            int x = s.top();
            s.pop();
            int y = b.top();
            b.pop();
            uniquein[icount] = y;
            in[icount++] = x;
        }
    }
    postorder(0, N - 1, 0, N - 1);
    return 0;
}

发表于 2021-01-20 22:06:52 回复(0)
初心者托奇头像 初心者托奇
代码在牛客上全部返回非零，本地运行没问题 
a = int(input())
c = input().split()[1]
d = {c:['','']}
m = [[c,1]]
for i in range(a * 2 - 1):
    b = input()
    if b != 'Pop':
        b = b.split()[1]
        d[m[-1][0]][m[-1][1]] = b
        d[b] = ['','']
    m[-1][1] -= 1
    if m[-1][1] == -1:
        del m[-1]
    if b != 'Pop':
        m.append([b,1])

i,n,p = 0,[[c,0]],[]
while True:
    while n[-1][1] == 2:
        del n[-1]
    p.append(n[-1][0])
    if len(p) == a:
        print(' '.join(p[::-1]))
        break
    while d[n[-1][0]][n[-1][1]] == '':
        n[-1][1] += 1
        if n[-1][1] == 2:
            del n[-1]
    n.append([d[n[-1][0]][n[-1][1]],0])
    n[-2][1] += 1
    if n[-2][1] == 2:
        del n[-2]


发表于 2020-03-10 16:24:29 回复(0)
SXGY_15头像 SXGY_15 
package pat.t0907;

import java.util.Scanner;
import java.util.Stack;

public class T4004 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Node root = null;
		Node current=null;
		Stack<Node> stack = new Stack<>();
		for (int i = 0; i < 2 * n; i++) {
			String line = sc.nextLine().trim();
			if (line.startsWith("Push")) {//"Push X"
				if (root == null) {
					root = new Node(Integer.parseInt(line.substring(5).trim()));
					current=root;
					stack.push(current);
					continue;
				}
				if (current.left== null) {
					current.left = new Node(Integer.parseInt(line.substring(5).trim()));
					current=current.left;
					stack.push(current);
				} else if (current.right== null) {
					current.right = new Node(Integer.parseInt(line.substring(5).trim()));
					current=current.right;
					stack.push(current);
				}
			} else if (stack.size() > 0) {//"Pop"
				current=stack.pop();
			}
		}
		sc.close();
		if(root!=null) {
			StringBuilder sb=root.toStringPostorder();
			sb.deleteCharAt(sb.length()-1);
			System.out.print(sb);
		}
	}
}

class Node {
	int data;
	Node left;
	Node right;
	Node(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
	public StringBuilder toStringPostorder() {//后序遍历
		StringBuilder sb=new StringBuilder();
		if(this.left!=null) {
			sb.append(this.left.toStringPostorder());
		}
		if(this.right!=null) {
			sb.append(this.right.toStringPostorder());
		}
		sb.append(this.data+" ");
		return sb;
	}
}
关键在于两个变量。current和stack，一个是当前操作的节点，一个是节点栈。
发表于 2019-09-08 09:42:17 回复(0)
Java
五十五郎头像 五十五郎


import java.util.*; public class treetravel { 
public static void main(String[] args){
Scanner input = new Scanner(System.in);
 int loopnum = input.nextInt(); 
 String non = input.nextLine(); 
 Stack stackr = new Stack(); 
 ArrayList resultlis=new ArrayList(); 
for (int i = 0; i 2 ; i++) {
String[] commlist = input.nextLine().split(" ");
 if(commlist[0].equals("Push")){
 int[] content=new int[2];
 content[0]=Integer.parseInt(commlist[1]);
 content[1]=0; stackr.push(content); 
}else if(commlist[0].equals("Pop")){
 while(!stackr.isEmpty()&&top(stackr)[1]==1){ 
int[] node=(int[])stackr.pop(); 
int value=node[0]; 
resultlis.add(value); 
 } settopval(stackr,1); }
}
 while(!stackr.isEmpty()){
 int[] node=(int[])stackr.pop(); 
int value=node[0]; resultlis.add(value); 
 }
 for(int i=0;i;i++){ 
if(i!=resultlis.size()-1){
System.out.print(resultlis.get(i)+" ");} 
else{
System.out.print(resultlis.get(i)); }
}
}
 public static int[] top(Stack stack){ 
int[] content= (int[]) stack.pop(); 
 stack.push(content);
 return content; }
 public static void settopval(Stack stack,int value){
 int[] content=(int[])stack.pop(); 
 content[1]=value;
 stack.push(content); }
}


发表于 2019-03-19 22:40:41 回复(0)
Disconnect头像 Disconnect 
class Node:
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right
def construct_tree(pre_order,s1,e1, mid_order,s2,e2):
  if s1>e1:
    return None
  i = mid_order.index(pre_order[s1])
  root_data = pre_order[s1]
  left = construct_tree(pre_order,s1+1,s1+i-s2, mid_order,s2,i-1)
  right = construct_tree(pre_order,s1+i-s2+1,e1, mid_order,i+1,e2)
  return Node(root_data, left, right)

def post(root):
    """递归后序遍历"""
    if root == None:
        return
    queue = []
    queue.append(root)
    while queue:
        node = queue.pop(0)
        if node.left:
            post(node.left)
        if node.right:
            post(node.right)
        print(data[node.value], end='')
#class Tree:
#    def __init__(self,root=None):
#        self.root = root
#    def post(self,tree):
#        """递归后序遍历"""
#        if tree is None:
#            return
#        queue = []
#        queue.append(tree)
#        while queue:
#            node = queue.pop(0)
#            if node.left:
#                self.post(self,node.left)
#            if node.right:
#                self.post(self,node.right)
#            print(data[node.value], end=' ')
n = input()
n = int(n)
num = 0
pre,inord,tem,data = [],[],[],[]
for i in range(2*n):
    t = input().split()
    if t[0]=="Push":
        pre.append(num)
        tem.append(num)
        data.append(int(t[1]))
        num+=1
    else:
        inord.append(tem.pop())
root = construct_tree(pre,0,n-1,inord,0,n-1)
post(root)
开始做这道题一直出错，后来看了大神的解答才明白过来掉了坑。
注意区分节点的 标号 和 值 。根据标号的前序中序重建二叉树，而不是值！！！
发表于 2018-12-23 11:22:10 回复(0)
小菜狗头像 小菜狗 
这题和pat的不是一道题
pat通过的代码：：
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#define N 100
using namespace std;
int parent[N];
vector<int> inorder;
queue<int> route;
void ReBuild(int root,vector<int>::iterator begin,vector<int>::iterator end)
{     vector<int>::iterator divid=find_if(begin,end,[root](int a)->bool{ return a==root;});     if(divid!=end)     {         vector<int>::iterator lt,rt;         lt=find_if(begin,divid,[root](int a)->bool{ return parent[a]==root;});         if(lt!=divid)             ReBuild(*lt,begin,divid);         rt=find_if(divid+1,end,[root](int a)->bool{ return parent[a]==parent[root];});         if(rt!=end)             ReBuild(*rt,divid+1,end);              }     route.push(root);      }
int main()
{     ifstream f("Input.txt");     cin.rdbuf(f.rdbuf());     int num;     cin>>num;     int root;     fill(parent,parent+N,0);     stack<int> operation;          for(int i=0;i<2*num;i++)     {         string op;         int id;         cin>>op;         if(op=="Push")         {             cin>>id;             operation.push(id);             if(i==0)                 root=id;         }         else         {             int node=operation.top();                 operation.pop();             inorder.push_back(node);             if(operation.size()==0)                 parent[node]=0;             else                 parent[node]=operation.top();         }     }                    ReBuild(root,inorder.begin(),inorder.end());     while(route.size())     {         if(route.size()==1)             cout<<route.front();         else              cout<<route.front()<<" ";         route.pop();     }     return 0;
}

发表于 2018-08-30 00:17:12 回复(0)
C/C++
Caffeine头像 Caffeine 
思路：这道题有一个坑点，就是创建二叉树的时候你要保证你的树没有相同的值，否则会报错。
我才用了就是建树的时候遇到相同的值后面加上一个".";
#include <ios>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<string> DLR(1);
vector<string> LDR(1);
int sum = 0;
typedef struct tagNODE {
    string value;
    struct tagNODE *pLeft, *pRight;
}NODE;

// 先序 和 中序 建立 树
NODE* GenBinTree(const int DLRStart, const int DLREnd, const int LDRStart, const int LDREnd)
{
    if(DLRStart > DLREnd || LDRStart > LDREnd)
    {
        return NULL;
    }
    
    if (DLRStart == DLR.size())
        return NULL;
    string rootValue = DLR[DLRStart];
    NODE *root = new NODE;
    root->value = rootValue;
    root->pLeft = root->pRight = NULL;
    int k;
    for (k = LDRStart; k <= LDREnd; k++)
    {
        if (LDR[k] == DLR[DLRStart])
            break;
    }
    int nl = k - LDRStart;
    root->pLeft = GenBinTree(DLRStart + 1, DLRStart + nl, LDRStart, k-1);
    root->pRight = GenBinTree(DLRStart + nl + 1, DLREnd, k + 1, LDREnd);
    return root;
}

void PostOrder(NODE *root)
{
    if (root != NULL)
    {
        PostOrder(root->pLeft);
        PostOrder(root->pRight);
        if (root->value.find(".") != string::npos)
        {
            root->value = root->value.substr(0, root->value.find("."));
        }

        if (--sum != 0)
            cout << root->value << " ";
        else
            cout << root->value << endl;
    }
}
int main()
{
    ifstream ifile("test.txt", ios::out | ios::in);// 文件要先存在
    
    string line;
    int n;
    while (cin >> n)
    {
        string temp;
        sum = n;
        string value;
        NODE *p = new NODE[n];
        stack<string> Mystack;

        for (int i = 0; i < n * 2; i++)
        {
            cin >> temp;
            if (temp == "Push")
            {
                cin >> value;
                for (int i = 1; i < DLR.size(); i++)
                {
                    if (DLR[i] == value)
                    {
                        value = value + ".";
                    }
                }
                DLR.push_back(value);
                Mystack.push(value);
            }
            if (temp == "Pop")
            {
                LDR.push_back(Mystack.top());
                Mystack.pop();
            }
        }
        /*
        for (auto c : DLR)
        {
            cout << c << " ";
        }
        cout << endl;
        for (auto c : LDR)
        {
            cout << c << " ";
        }
        cout << endl;
        */
        NODE *root = GenBinTree(1, LDR.size() - 1, 1, LDR.size() - 1);
        // 后根遍历
        PostOrder(root);
    }
    ifile.close();
    //cout.close();
    system("pause");
}

发表于 2018-08-16 19:38:44 回复(0)
C/C++
EricMaC头像 EricMaC
#include<stdio.h>
#include<string.h>
#include<stack>
int pre[31];
int in[31];
//  pat's test data has unique node number(1-n), but niuke is not
int data[31];//key-value

int n;int num=0;
void postTravel(int p1,int p2,int i1,int i2){
    if(p2-p1<0)
        return;
    if(p2-p1==0){
        printf("%d",data[pre[p1]]);
        num++;
    }else if(p2-p1==1){
        printf("%d ",data[pre[p2]]);
        printf("%d",data[pre[p1]]);
        num++;num++;
    }else if(p2-p1>=2){
        int root=pre[p1];
        int i=i1;
        for(;i<=i2&&i<n;i++)
        {if(in[i]==root)
            break;
        }

        postTravel(p1+1,p1+1+(i-1-i1),i1,i-1);//left
        postTravel(p1+1+(i-1-i1)+1,p2,i+1,i2);//right

        printf("%d",data[root]);
        num++;
    }
    if(num!=n)
        printf(" ");
}
int main(){
    scanf("%d",&n);
    int put=0,popt=0;
    std::stack<int> st;
    char s[30]={0};
    for(int i=0;i<2*n;i++){
        scanf("%s",s);
        if(strcmp(s,"Push")==0){
            int t=0;
            scanf("%d",&t);
            st.push(put);pre[put]=put;data[put]=t;put++;
        }else{
            in[popt++]=st.top();
            st.pop();
        }
    }
    postTravel(0,n-1,0,n-1);
    return 0;
}
编辑于 2018-07-24 22:03:18 回复(0)
zhaomengmeng头像 zhaomengmeng 
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode() = default;
	TreeNode(const int v) : val(v)
	{
		left = NULL;
		right = NULL;
	}

};

TreeNode* RecoveryTree(const vector<int> & preOrder, const int b1, const int e1,
	const vector<int> & inOrder, const int b2, const int e2)
{
	if (b1 > e1)
		return NULL;
	int idx = distance(inOrder.begin(), find(inOrder.begin(), inOrder.end(), preOrder[b1]));

	TreeNode* root = new TreeNode(preOrder[b1]);
	root->left = RecoveryTree(preOrder, b1 + 1, b1 + idx - b2, inOrder, b2, idx - 1);
	root->right = RecoveryTree(preOrder, b1 + idx - b2 + 1, e1, inOrder, idx + 1, e2);

	return root;
}

TreeNode* BuildTree(int *N)
{
	TreeNode* root = NULL;

	//fstream f1("test1.txt");

	//f1 >> *N;
	stack<int> s;
	vector<int> preOrder, inOrder;
	string line, word;
	string Pop("Pop"), Push("Push");
	int id;

	getline(cin, line);
	istringstream in(line);
	in >> *N;

	for (int i = 0; i < *N * 2; i++)
	{
		//f1 >> word;
		getline(cin, line);
		istringstream in(line);
		in >> word;
		if (word == Push)
		{
			//f1 >> id;
			in >> id;
			s.push(id);
			preOrder.push_back(id);
		}
		else if (word == Pop)
		{
			int a = s.top();
			s.pop();
			inOrder.push_back(a);
		}
	}

	root = RecoveryTree(preOrder, 0, preOrder.size() - 1, inOrder, 0, inOrder.size() -1);

	return root;
}

void PostOrderTraversal(const TreeNode * root, int &count, const int N)
{
	if (root)
	{
		PostOrderTraversal(root->left, count, N);
		PostOrderTraversal(root->right, count, N);
		count++;
		if (count != N)
			cout << root->val << " ";
		else
			cout << root->val << endl;
	}

}
void DestroyTree(TreeNode * root)
{
	if (!root)
		return;
	DestroyTree(root->left);
	DestroyTree(root->right);
	delete root;
	root = NULL;
}

int main()
{
	TreeNode* root;
	int count = 0;
	int N = 0;
	
	root = BuildTree(&N);
	PostOrderTraversal(root, count, N);
	DestroyTree(root);

	return 0;
}

发表于 2017-04-09 14:27:05 回复(0)
Java
jarviswong头像 jarviswong
Java代码，通过所有测试。 
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

class Tree {
    int val;
    Tree left;
    Tree right;

    public Tree(int val) {
        this.val = val;
    }

    public Tree() {}
}

public class Main {
    public static void postorder(Tree root, ArrayList list) {
        if (root != null) {
            postorder(root.left, list);
            postorder(root.right, list);
            list.add(root.val);
        }
    }

    public static void main(String args[]) {
        ArrayList list = new ArrayList();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  //input N nodes
        Stack stack = new Stack();
        String str = new String("");
        Tree[] root = new Tree[n + 1];
        int index = 0;
        int popVal = -1;
        for (int i = 0; i < 2 * n; ++i) {
            str = sc.next();
            if (str.equals("Push")) {
                int value = sc.nextInt();
                if (i == 0) {
                    root[++index] = new Tree(value);
                } else if (i != 0 && popVal == -1) {
                    root[(Integer) stack.peek()].left = root[++index] = new Tree(value);
                }
                if (popVal != -1) {
                    root[popVal].right = root[++index] = new Tree(value);
                }
                stack.push(index);
                popVal = -1;
            } else {
                popVal = (Integer) stack.peek();
                stack.pop();
            }
        }
        postorder(root[1], list);
        for (int i = 0; i < list.size(); ++i) {
            if (i != list.size() - 1)
                System.out.print(list.get(i) + " ");
            else
                System.out.print(list.get(i));
        }
    }
}
发表于 2016-10-14 23:43:33 回复(0)
提交观点

问题信息

树
难度：
22条回答 13361浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号