We can construct the tree recursively by dividing the preorder traversal array into two parts: one representing the left subtree and the other representing the right subtree. Then, we construct the left and right subtrees recursively. The root of the tree is the first element in the preorder traversal array. The mirror tree's preorder traversal helps in identifying the structure of the original tree.
Example Code in Python:
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
def construct_full_binary_tree(preorder, mirror_preorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
if len(preorder) == 1:
return root
# Find the index where the right subtree starts
mirror_root_val = mirror_preorder[0]
idx = preorder.index(mirror_root_val)
# Construct left and right subtrees recursively
root.left = construct_full_binary_tree(preorder[1:idx], mirror_preorder[1:idx])
root.right = construct_full_binary_tree(preorder[idx:], mirror_preorder[idx:])
return root
def print_preorder(node):
if node:
print(node.val, end=" ")
print_preorder(node.left)
print_preorder(node.right)
# Example usage:
preorder = [1, 2, 4, 5, 3, 6, 7]
mirror_preorder = [1, 3, 7, 6, 2, 5, 4]
root = construct_full_binary_tree(preorder, mirror_preorder)
print("Preorder Traversal of Full Binary Tree:")
print_preorder(root)
Explanation:
- The TreeNode class represents a node in the binary tree.
- The construct_full_binary_tree function takes the preorder traversal array of the original tree and its mirror tree as input and constructs the full binary tree.
- print_preorder function is used to print the preorder traversal of the constructed full binary tree.
- Example usage demonstrates how to use the construct_full_binary_tree function with given preorder traversals to construct the tree and print its preorder traversal.
