TREEORD - Tree _order


Description

A tree is a connected acyclic graph.
A binary tree is a tree for which each node has a left child, a right child, both, or neither, e.g.
    1
   / \
  2   3
 / \   \
4   5   6
There are three common ways to recursively traverse such a tree.
  1. Pre-order: parent, left subtree, right subtree
  2. Post-order: left subtree, right subtree, parent
  3. In-order: left subtree, parent, right subtree
Given pre-order, post-order, and in-order traversals, determine if they can be of the same binary tree.
For example,
1 2 4 5 3 6
4 5 2 6 3 1
4 2 5 1 3 6
are the pre-order, post-order, and in-order traversals of the tree above.
But
1 2 4 5 3 6
4 5 2 6 1 3
4 2 5 1 6 3
cannot be the pre-order, post-order, and in-order traversals of the same binary tree.

Input

The first line is the number of nodes in each traversal, 0 < N <= 8000.
The second line is the N space separated nodes of the pre-order traversal.
The third line is the N space separated nodes of the post-order traversal.
The fourth line is the N space separated nodes of the in-order traversal.
Each traversal is a sequence of the nodes, numbered 1 to N, without repetition.

Output

Print "yes" if all three traversals can be of the same tree, and "no" otherwise.
Input Input
6
1 2 4 5 3 6
4 5 2 6 3 1
4 2 5 1 3 6
6
1 2 4 5 3 6
4 5 2 6 1 3
4 2 5 1 6 3
Output Output
yes
no

hide comments
cnexans: 2016-08-04 06:57:48

I found it tricky. Finally AC.

kartikay singh: 2016-06-30 20:50:36

Nice problem :-)
Easy recursion

naufalpf: 2016-04-09 14:20:36

y

sumbayak_ae: 2016-04-07 14:12:42

Sesi Lab, ez :v

Last edit: 2016-04-07 14:27:26
sumbayak_ae: 2016-04-07 14:09:54

AC in one go. Nice problem. Think of recursion ;D

Archit Gupta: 2016-02-26 11:04:52

AC in first attempt easy prob 150th on spoj!

:.Mohib.:: 2016-01-02 12:03:35

Like it...!!

kejriwal: 2015-10-10 19:22:59

nice and elegant (: !!

Jaswanth: 2015-08-21 11:19:38

nice concept on trees.

rini22: 2015-07-06 10:11:25

AC :)


Added by:BYU Admin
Date:2014-02-23
Time limit:0.5s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64