C# Recursive Solution with Dictionary

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
Dictionary<int,int> dict = new Dictionary<int,int>();
int preorderIndex = 0;

public TreeNode BuildTree(int[] preorder, int[] inorder) {
if(preorder.Length == 0) {
return null;
}

for(int i = 0; i < inorder.Length; i++) {
dict[inorder[i]] = i;
}

TreeNode root = new TreeNode(preorder[0]);
preorderIndex = 0;
helper(root, preorder, 0, preorder.Length - 1);
return root;

}

private void helper(TreeNode node, int[] preorder, int min, int max) {
if(preorderIndex + 1 >= preorder.Length) {
return;
}
int childIndex = dict[preorder[preorderIndex + 1]];
if(childIndex < dict[node.val] && childIndex <= max && childIndex >= min) {
preorderIndex++;
node.left = new TreeNode(preorder[preorderIndex]);
helper(node.left, preorder, min, dict[node.val] - 1);
}
if(preorderIndex + 1 >= preorder.Length) {
return;
}
childIndex = dict[preorder[preorderIndex + 1]];
if(childIndex > dict[node.val] && childIndex <= max && childIndex >= min) {
preorderIndex++;
node.right = new TreeNode(preorder[preorderIndex]);
helper(node.right, preorder, dict[node.val] + 1, max);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.