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.

For example, given

inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]

Return the following binary tree:

3   / \  9  20    /  \   15   7 题意：通过中序遍历和后序遍历构建二叉搜索树 代码如下：

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {number[]} inorder * @param {number[]} postorder * @return {TreeNode} */var buildTree = function(inorder, postorder) {            return backtrack(inorder,0,inorder.length-1,postorder,0,postorder.length-1);    }var backtrack = function( inorder,  inStart,inEnd , postorder, postStart, postEnd){       if(inStart>inEnd || postStart>postEnd){           return null;       }      let root = new TreeNode(postorder[postEnd]);        let inIndex=0;        for(let i=inStart;i<=inEnd;i++){            if(inorder[i]==root.val){                inIndex=i;            }        }        root.left=backtrack(inorder,inStart,inIndex-1,postorder,postStart,postStart+inIndex-inStart-1);        root.right=backtrack(inorder,inIndex+1,inEnd,postorder,postStart+inIndex-inStart,postEnd-1);        return root;    }