Construct Binary Tree

105. Construct Binary Tree from Preorder and Inorder Traversal

 public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0) return null;

    int num = preorder[0];
    int len = 0;
    for(int i=0; i<inorder.length; i++){
        if(inorder[i] == num)
            len = i;
    }

    TreeNode node = new TreeNode(num);
    node.left = buildTree(Arrays.copyOfRange(preorder, 1, 1+len),
                         Arrays.copyOfRange(inorder, 0, len));
    node.right = buildTree(Arrays.copyOfRange(preorder, 1+len, preorder.length),
                        Arrays.copyOfRange(inorder, 1+len, inorder.length));
    return node;
}

106. Construct Binary Tree from Inorder and Postorder Traversal

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(postorder.length == 0) return null;

    int n = postorder[postorder.length-1];
    int len = 0;
    for(int i=0; i<inorder.length; i++){
        if(inorder[i] == n) len = i;
    }

    TreeNode root = new TreeNode(n);
    root.left = buildTree(Arrays.copyOfRange(inorder, 0, len), 
                          Arrays.copyOfRange(postorder, 0, len));
    root.right = buildTree(Arrays.copyOfRange(inorder, len+1, inorder.length),
                           Arrays.copyOfRange(postorder, len, postorder.length-1));
    return root;
}

889. Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.

Example

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]

• find the length of left tree and use it split the left tree and right tree

• Preorder and postorder left tree length are the same, and pre[1] the head of left tree, use is to find the last position in postorder

public TreeNode constructFromPrePost(int[] pre, int[] post) {
    // pre  [1][2,4,5][3,6,7]
    // post [4,5,2][6,7,3][1]

    int len = pre.length;
    if(len == 0) return null;
    TreeNode node = new TreeNode(pre[0]);
    if(len == 1) return node;

    // find out the length of left tree
    int left_len = 0;
    for(int i=0; i<len; i++){
        if(post[i] == pre[1]) left_len = i+1;
    }

    node.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1+left_len), 
                                        Arrays.copyOfRange(post, 0, left_len));
    node.right = constructFromPrePost(Arrays.copyOfRange(pre, 1+left_len, len),
                                         Arrays.copyOfRange(post, left_len, len-1));
    return node;
}