101
0/320
Loading content...
You are given two integer arrays representing the traversal sequences of the same binary tree:
Your task is to reconstruct the original binary tree using these two traversal sequences and return the root node of the rebuilt tree.
The key insight is that in preorder traversal, the first element is always the root of the tree (or subtree). In inorder traversal, all elements to the left of the root belong to the left subtree, and all elements to the right belong to the right subtree. By combining this information, you can recursively partition the arrays and rebuild the entire tree structure.
Important: All node values in the tree are unique, which means each value appears exactly once in both traversal arrays. This uniqueness property is essential for unambiguously reconstructing the tree.
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7][3,9,20,null,null,15,7]From preorder, we know 3 is the root. In inorder, 9 is to the left of 3 (left subtree) and [15,20,7] are to the right (right subtree). Continuing recursively: the left subtree has only node 9. For the right subtree, preorder tells us 20 is the root, and inorder shows 15 is left of 20, 7 is right of 20. The final tree has 3 as root, with 9 as left child and 20 as right child. Node 20 has left child 15 and right child 7.
preorder = [-1]
inorder = [-1][-1]With only one element, the tree consists of a single node with value -1.
preorder = [1,2,3]
inorder = [2,1,3][1,2,3]From preorder, 1 is the root. In inorder, 2 appears before 1 (left subtree) and 3 appears after 1 (right subtree). So the tree has root 1, with left child 2 and right child 3.
Constraints