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.
- Pre-order: parent, left subtree, right subtree
- Post-order: left subtree, right subtree, parent
- 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 6are 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 3cannot 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.
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 :-)
|
|
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 |