C# Recursive Solution with Dictionary


  • 0
    K
    /**
     * 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);
            }
        }
    }
    

Log in to reply
 

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