#TREEORD. Tree _order
Tree _order
<style> .center { margin-right: auto; margin-left: auto; } .example-table { margin-top: 10px; text-align: left; width: 100%; } .example-table td { max-width: 0; word-wrap: break-word; vertical-align: top; } .example-table .vertical-spacer { height: 5px; } .section { margin-top: 19px; margin-bottom:19px; } .section:first-child, .section:first-child > h3:first-child { margin-top: 0; } .paragraph { margin-top: 10px; margin-bottom: 10px; text-align: left; } .paragraph ul, .paragraph pre { margin-top: 3px; margin-bottom: 3px; } pre { tab-size: 4; } .billboard { line-height: 1em; outline: solid 1px black; } </style>本题没有可用的提交语言。
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.
- Preorder: parent, left subtree, right subtree
- Postorder: left subtree, right subtree, parent
- Inorder: left subtree, parent, right subtree
Given preorder, postorder, and inorder 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 preorder, postorder, and inorder 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 preorder, postorder, and inorder tranversals of the same binary tree.
<div class="section">
<h3>Input</h3>
<div class="paragraph">
The first line is the number of nodes in each traversal, 0 < N <= 8000.
<br>
The second line is the N space seperated nodes of the preorder traveral.
<br>
The third line is the N space separated nodes of the postorder traversal.
<br>
The fourth line is the N space separated nodes of the inorder traversal.
</div>
<div class="paragraph">
Each traversal is a sequence of the nodes, numbered 1 to N, without repitition.
</div>
</div>
<div class="section">
<h3>Output</h3>
<div class="paragraph">
Print "yes" if all three traversals can be of the same tree, and "no" otherwise.
</div>
</div>
<table class="section example-table">
<tbody><tr>
<th>Input</th>
<th>Input</th>
</tr>
<tr>
<td>
6 1 2 4 5 3 6 4 5 2 6 3 1 4 2 5 1 3 6
</td>
<td>
6 1 2 4 5 3 6 4 5 2 6 1 3 4 2 5 1 6 3
</td>
</tr>
<tr>
<th>Output</th>
<th>Output</th>
</tr>
<tr>
<td>
yes
</td>
<td>
no
</td>
</tr>
</tbody></table>