public class Solution {
Dictionary<int, int> inorder_indexes = new ();
public TreeNode BuildTree(int[] preorder, int[] inorder) {
for (var i = 0; i < preorder.Length; i++)
{
inorder_indexes.Add(inorder[i], i);
}
return build(preorder, 0, preorder.Length-1, inorder, 0, inorder.Length - 1);
}
TreeNode build(int[] preorder, int preorder_left, int preorder_right, int[] inorder, int inorder_left, int inorder_right)
{
//Console.WriteLine($"{preorder_left} - {preorder_right}; {inorder_left} - {inorder_right}");
if (preorder_left > preorder_right || inorder_left > inorder_right)
return null;
TreeNode node = new TreeNode { val = preorder[preorder_left] };
int node_inorder_index = inorder_indexes[node.val];
int left_length = node_inorder_index - inorder_left;
int right_length = inorder_right - node_inorder_index;
node.left = build(preorder,
preorder_left + 1,
preorder_left + left_length,
inorder,
inorder_left,
inorder_left + left_length - 1);
node.right = build(preorder,
preorder_right - right_length + 1,
preorder_right,
inorder,
inorder_right - right_length + 1,
inorder_right);
return node;
}
}