Loading...
You are given two lists of unique integers, preorder and inorder, both containing the same values from a binary tree. preorder lists each node before its left and right subtrees. inorder lists the left subtree, then the node, then the right subtree.
Build the tree and return its root.
You can assume preorder and inorder always describe exactly one binary tree, so the answer is unique.
Your function returns the root of the tree as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below show the returned tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the tree is displayed; the encoding is done for you.
preorder.length = inorder.lengthpreorder[i], inorder[i] ≤109preorder are unique, and inorder is a permutation of preorder.preorder and inorder are the preorder and inorder traversals of some binary tree.The root is `3`, since it comes first in `preorder`. In `inorder`, `9` sits before `3` and `15, 20, 7` sit after, so `9` is the whole left subtree and `15, 20, 7` form the right subtree, which itself splits into `20` with left child `15` and right child `7`.
Every value in `inorder` comes before the root `3`, so the whole tree is a left-only chain: `3` has left child `2`, which has left child `1`.
The value after the root `1` in `inorder` belongs to the right subtree, so `2` becomes the right child of `1`.