Rebuild a Binary Tree From Two Walks
Problem statement
A binary tree has different values in all its nodes. You are given two walks of it:
preorder: visit a node, then its left subtree, then its right subtree.inorder: visit the left subtree, then the node, then the right subtree.
Rebuild the tree and return its root. Because all values are different, exactly one tree fits both walks.
Function
buildTree(preorder: int[], inorder: int[]) → TreeNodeExamples
Example 1
preorder = [5,9,2,7,4]inorder = [2,9,5,4,7]return = [5,9,7,2,null,4]Preorder starts with the root, 5. In the inorder list, 2 and 9 come before 5, so they form the left subtree; 4 and 7 come after, so they form the right subtree. The left part of preorder is [9, 2]: 9 is its root and 2 its left child. The right part is [7, 4]: 7 is its root and 4 its left child.
Example 2
preorder = [4,6]inorder = [6,4]return = [4,6]4 is the root. In inorder, 6 comes before 4, so 6 is in the left subtree: it is the left child of 4.
Example 3
preorder = [1,2,3]inorder = [1,2,3]return = [1,null,2,null,3]Each root comes first in its part of the inorder list, so no node has a left subtree; each next preorder value is the right child of the one before, a chain to the right.
Constraints
1 <= preorder.length <= 800andinorder.length == preorder.length-10^4 <= preorder[i], inorder[i] <= 10^4- All values are different, and
inorderholds the same values aspreorder. - The two lists are the preorder and inorder walks of one binary tree.