106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
根据中序和后序遍历来构建二叉树。
后序遍历的最后是跟节点，在中序遍历中找到这个节点，这个节点的左边就是左子树，右边就是右子树；
根据左子树和右子树的长度，可以在后序遍历中把属于左子树的后序遍历和右子树的后序遍历找出来；
继续递归。

var buildTree = function(inorder, postorder) {
    if (inorder === null || postorder === null || inorder.length != postorder.length)
        return null;
    var hm = {};
    for (var i=0;i<inorder.length;++i)
        hm[inorder[i]] = i;
    return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1,hm);
    function buildTreePostIn(inorder, is, ie, postorder, ps, pe, hm){
        if (ps > pe || is > ie) return null;
        var root = new TreeNode(postorder[pe]);
        var ri = hm[postorder[pe]];
        var leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
        var rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
        root.left = leftchild;
        root.right = rightchild;
        return root;
    }
};

还有一个神奇的答案我没看懂

var buildTree = function(inorder, postorder) {
    var pInorder;   // index of inorder array
    var pPostorder; // index of postorder array
    function help(inorder, postorder, end) {
        if (pPostorder < 0) {
            return null;
        }
        // create root node
        var n = new TreeNode(postorder[pPostorder--]);
        // if right node exist, create right subtree
        if (inorder[pInorder] !== n.val) {
            n.right = help(inorder, postorder, n);
        }
        pInorder--;
        // if left node exist, create left subtree
        if ((end === null) || (inorder[pInorder] !== end.val)) {
            n.left = help(inorder, postorder, end);
        }
        return n;
    }
    pInorder = inorder.length - 1;
    pPostorder = postorder.length - 1;
    
    return help(inorder, postorder, null);
};

105. Construct Binary Tree from Preorder and Inorder Traversal.

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
这个用前序遍历和中序遍历构建二叉树
同样的思想：

var buildTree = function(preorder, inorder) {
    if (inorder === null || preorder === null || inorder.length != preorder.length)
        return null;
    var hm = {};
    for (var i=0;i<inorder.length;++i)
        hm[inorder[i]] = i;
    return help(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1,hm);
    function help(inorder, is, ie, preorder, ps, pe, hm){
        if (ps > pe || is > ie) return null;
        var root = new TreeNode(preorder[ps]);
        var ri = hm[preorder[ps]];
        var leftchild = help(inorder, is, ri-1, preorder, ps+1, ps+ri-is, hm);
        var rightchild = help(inorder,ri+1, ie, preorder, ps+ri-is+1, pe, hm);
        root.left = leftchild;
        root.right = rightchild;
        return root;
    }
};