Build a tree with preliminary traversal

Question

A special type of tree is indicated where all leaves are marked with L and others are marked with N Each node can have 0 or no more than 2 nodes. A preposition walk for the tree is provided.

Give an algorithm to build a tree from this bypass.

Answer 1

This is an order traversal algorithm:

 Preorder(T) if (T is not null) print T.label Preorder(T.left) Preorder(T.right) 

Let's try to find an algorithm for entering NNLLNL .

Obviously, the root label is printed first. So, you know that the root has the label N Now the algorithm repeats in the left subtree. It is also N according to the input. Repair the left subtree of what is L Now you need to step back because you have reached the leaf. The next input position is also L , so the current node has a right child with the label L The return trip once. Rollback again because you added all the children of the current node (maximum 2 children). Now you are again at the root. You must go straight because you have already gone left. According to the input, this is N Thus, the correct root of the root N His left number will be L This is your tree:

  N / \ NN / \ / LLL 

Please note that the solution is not necessarily unique, but it will help you find a solution.

pseudo code:

 k = 0 input = ... get preorder traversal vector from user ... Reconstruct(T) if input[k] == N T = new node with label N k = k + 1 Reconstruct(T.left) Reconstruct(T.right) else T = new node with label L T.left = T.right = null k = k + 1 

A call with a zero node.

Follow-up question : for both pre-ordering and traversing the order of a binary tree containing various node labels, how can you uniquely restore a tree?

Answer 2

Here is my version of golang that was used to solve many tree problems in leetcode.

 // NewPreorderTree returns preorder tree relate to nums, nums must has not Ambiguity. // -1 in nums represents child is null. // // Example 1: // Input: [1, 2, 3] // Generate: // 1 // / // 2 // / // 3 // // Example 2: // Input: [1, 2, -1, -1, 3] or [1, 2, -1, -1, 3, -1, -1] // Generate: // 1 // / \ // 2 3 func NewPreorderTree(nums ...int) *TreeNode { return (&preorderTree{nums}).constructTree() } type preorderTree struct { nums []int } func (p *preorderTree) constructTree() *TreeNode { if len(p.nums) == 0 { return nil } if p.nums[0] == -1 { p.nums = p.nums[1:] return nil } root := &TreeNode{Val: p.nums[0]} p.nums = p.nums[1:] root.Left = p.constructTree() root.Right = p.constructTree() return root }