首页 > 试题广场 >

Tree Traversals Again (25)

[编程题]Tree Traversals Again (25)

热度指数：4008 时间限制：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

算法知识视频讲解

查看答案及解析

推荐

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)

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)

Java

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)