105. Construct Binary Tree from Preorder and Inorder Traversal

[LLancelot]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// root->left>right, preorder = [3,9,20,15,7]
// left->root->right, inorder = [9,3,15,20,7]
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // HashMap to store indicies(9,0),(3,1),(15,2)...
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i], i);
        
        return build(preorder, inorder, 0, 0, inorder.length-1, map);
    }
    
    private TreeNode build(int[] preorder, int[] inorder,
                           int preBegin, int inBegin, int inEnd, HashMap<Integer, Integer> map){
        // return case
        if (preBegin >= preorder.length || inBegin > inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preBegin]);
        // root_index: get root num index from inorder(map)
        int root_index = map.get(preorder[preBegin]);
        // build the tree
        root.left = build(preorder, inorder, preBegin+1, inBegin, root_index-1, map);
        root.right = build(preorder, inorder, preBegin + root_index-inBegin+1, root_index+1, inEnd, map);
        
        return root;
      }
}

[LLancelot]

106

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*; 

import java.util.ArrayList;
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // HashMap to store indicies(9,0),(3,1),(15,2)...
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i], i);
        
        // for(int i=0; i<postorder.length/2; i++){
        //     int temp = postorder[i];
        //     postorder[i] = postorder[postorder.length -i -1];
        //     postorder[postorder.length -i -1] = temp;
        // }
        int size = postorder.length;
        int[] reverse = new int[size];
        for (int i=size-1; i>=0;i--)
            reverse[size-1-i] = postorder[i];
        
        return build(reverse, inorder, 0, 0, inorder.length-1, map);
    }
    
    private TreeNode build(int[] postorder, int[] inorder,
                           int postBegin, int inBegin, int inEnd, HashMap<Integer, Integer> map){
        // return case
        if (postBegin >= postorder.length || inBegin > inEnd)
            return null;
        TreeNode root = new TreeNode(postorder[postBegin]);
        // root_index: get root num index from inorder(map)
        int root_index = map.get(postorder[postBegin]);
        // build the tree
        root.right = build(postorder, inorder, postBegin+1, root_index+1,inEnd, map);
        root.left = build(postorder, inorder, postBegin + inEnd-root_index+1, inBegin, root_index - 1, map);
        
        return root;
    }
}

[ytp327]

105

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return None
        temp=preorder.pop(0)
        index=inorder.index(temp)
        node=TreeNode(temp)
        node.left=self.buildTree(preorder,inorder[:index])
        node.right=self.buildTree(preorder,inorder[index+1:])
        return node