Construct tree with pre-order traversal given
A special type of tree is given where all leaves are marked with L
and others are marked with N
. Every n开发者_开发百科ode can have 0 or at most 2 nodes. The preorder traversal of the tree is given.
Give an algorithm to build the tree from this traversal.
This is the preorder 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 an input of NNLLNL
.
Obviously the label of the root is printed first. So you know the root has label N
. Now the algorithm recurses on the left subtree. This is also N
according to the input. Recurse on the left subtree of that, which is L
. Now you have to backtrack, because you've reached a leaf. The next position in the input is also L
, so the current node has a right child labeled with L
. Backtrack once. Backtrack again, because you've added all the children of the current node (max 2 children). Now you're at the root again. You have to go right, because you already went left. According to the input, this is N
. So the right child of the root is N
. The left child of that will be L
. This is your tree:
N
/ \
N N
/ \ /
L L L
Note that the solution is not necessarily unique, but this will get you a possible solution.
Pseudocode:
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
Call with a null node.
Follow-up question: given both the preorder and the inorder traversal of a binary tree containing distinct node labels, how can you uniquely reconstruct the tree?
Here is my golang version which was used to solve many problems about tree 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
}
精彩评论