Consider a binary tree with N nodes, each labeled with a distinct integer between 1 and N, inclusive.
We can convert the tree into a sequence of labels by traversing the tree in a particular
order, but there are many possible orders. Two common orders are in-order traversal
and breadth-first traversal, defined as follows:
- In-Order: Begin by visiting the root. As you visit each node, first recursively visit its left child (if it has one),
then output the node's label, then recursively visit its right child (if it has one).
- Breadth-First: First output the label of the root, then the labels of the root's children,
then the labels of the root's grandchildren, its great-grandchildren, and so on. Among nodes on the same level,
output the labels from left to right.
For example, given the tree
1
/ \
2 4
/ / \
3 5 7
\
6
an in-order traversal would produce the sequence 3,2,1,5,6,4,7 and a breadth-first traversal would produce the
sequence 1,2,4,3,5,7,6.
Given the output of a particular traversal, we cannot always tell which of several possible trees we started with. However,
given the output of both an in-order traversal and a breadth-first traversal of the same tree, we can uniquely reconstruct
the tree. You are to write a method that takes the output of an in-order
traversal, inOrder, and the output of a breadth-first traversal, breadthFirst, and returns the width of the tree,
defined as the maximum number of nodes on any one level of the tree. For example, the tree above has width 3, achieved by the level containing the values 3, 5, and 7.
If we start with the output of an in-order traversal from one tree and a breadth-first traversal from a different tree,
it is not always possible to reconstruct a single tree that is compatible with both sequences. If no tree exists that could have produced both traversals,
return -1.
|