（团体程序设计天梯赛）L2-011 玩转二叉树（25 分)

绝地灬酷狼 2021-12-24 18:43 235阅读 0赞

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

#### 输入格式： ####

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

#### 输出格式： ####

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

#### 输入样例： ####

> 7  
> 1 2 3 4 5 6 7  
> 4 1 3 2 6 5 7

#### 输出样例： ####

> 4 6 1 7 5 3 2

因为输出的是镜像，所以只需让右子树先进队即可。其它几乎和[(团体程序设计天梯赛)L2-006 树的遍历][L2-006]  
一样，只是一个给前序遍历，一个给后序遍历。其它基本没差别

import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Main { 
    	static StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
    
    	static int bc[];
    
    	public static void main(String[] args) { 
    		int n = nextInt();
    		int q[] = new int[n+1];
    		int z[] = new int[n+1];
    		for(int i = 0;i<n;i++) { 
    			z[i] = nextInt();
    		}
    		for(int i = 0;i<n;i++) { 
    			q[i] = nextInt();
    		}
    		int c[] = new int[n+1];
    		Queue<Node> que = new LinkedList<Node>();
    		que.add(new Node(0, n, 0, n));
    		int cont = 0;
    		while(!que.isEmpty()) { 
    			Node te = que.poll();
    			c[cont++] = q[te.ql];
    			for(int i = te.zl;i<te.zr;i++) { 
    				if(z[i]==q[te.ql]) { 
    					if(i<te.zr-1) { 
    						que.add(new Node(i-te.zl+te.ql+1, te.qr, i+1, te.zr));						
    					}
    					if(i>te.zl) { 
    						que.add(new Node(te.ql+1, i-te.zl+te.ql, te.zl, i));
    					}
    					
    					break;
    				}
    			}
    		}
    		System.out.print(c[0]);
    		for(int i = 1;i<n;i++) { 
    			System.out.print(" "+c[i]);
    		}
    	}
    
    	static int nextInt() { 
    		try { 
    			st.nextToken();
    		} catch (IOException e) { 
    			e.printStackTrace();
    		}
    		return (int) st.nval;
    	}
    
    	static String next() { 
    		try { 
    			st.nextToken();
    		} catch (IOException e) { 
    			e.printStackTrace();
    		}
    		return st.sval;
    	}
    }
    class Node{ 
    	int ql;
    	int qr;
    	int zl;
    	int zr;
    	public Node(int ql, int qr, int zl, int zr) { 
    		this.ql = ql;
    		this.qr = qr;
    		this.zl = zl;
    		this.zr = zr;
    	}
    	@Override
    	public String toString() { 
    		return "Node [ql=" + ql + ", qr=" + qr + ", zl=" + zl + ", zr=" + zr + "]";
    	}
    	
    }

转载于:https://www.cnblogs.com/xfx98/p/10589993.html

[L2-006]: https://blog.csdn.net/qq_40827780/article/details/88312744