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; }
106. Construct Binary Tree from Inorder and Postorder Traversal（js）
原文：https://www.cnblogs.com/xingguozhiming/p/10713140.html