You are viewing a single comment's thread. Return to all comments →
Well I disagree. I've found many "easy" problems considerably more difficult than this one. I don't really understand the confusion with reading the input.
First, I used a Node class, which held the level for each node (along with the label and left and right children). Then stored the nodes as an array of Nodes (seemed pretty obvious considering the labeling). Finally I used a Map (HashMap) which held a list of nodes at each level.
So reading was pretty straightforward: iterate 0-N to get children. Each time you are setting the children of node[i], further you can set the level of the children by adding one to node[i]'s level. Add the children nodes to the list for that particular level.
Then swapping is incredibly easy: find the list at each level and swap all of those nodes' children. Use previous algorithm (or in my case a much simpler recursive algorithm) to print the new tree in-order.
I know space-wise, that's definitely not the most efficient. But in terms of time-complexity, the most expensive operation is printing the tree.
The one part that I thought about that could have made it more difficult is if they didn't give the nodes "in order" (which I see no where that this was necessary). So for instance, the second node might not have had it's level set when it's children were specified (say because the first node didn't contiain node "2"). I figured if that was the case, you could do some kind of bubble iteration after all of the nodes were parsed. Basically keep iterating through all of the nodes until all of the levels were set