A binary tree was walked twice, and you get both records of the walk:
preorder lists the values in preorder: a node first, then its whole left subtree, then its whole right subtree.inorder lists the values in inorder: a node's whole left subtree first, then the node, then its whole right subtree.No two nodes hold the same value. Rebuild the tree and return its root.
preorder starts with 10, so 10 is the root. In inorder, the values before 10 (2, 4, 7) form its left subtree and the values after it (12, 15) form its right subtree. The same split, repeated inside each part, places every other node.
1 comes last in inorder, so everything else is in its left subtree, and 3 comes after 2 there, so 3 is the right child of 2.
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder are distinct, and inorder holds the same values.The first value in preorder is the root. Find it in inorder: everything to its left there is the left subtree and everything to its right is the right subtree. The left part's size tells you where each subtree's values sit in preorder.
Each list on its own loses the shape. Together they pin it down, because each one answers a different question.
Time O(n)Space O(n)
The full walkthrough and code are part of Premium