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.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
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[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree = function(preorder, inorder) { return backtrack(0,0,preorder.length-1,preorder,inorder); } var backtrack = function(preIndex,inStart,inEnd, preorder, inorder){ if(preIndex>preorder.length-1 || inStart>inEnd){ return null; } let root=new TreeNode(preorder[preIndex]); let inIndex=0; for(let i=inStart;i<=inEnd;i++){ if(inorder[i]==root.val){ inIndex=i; } } root.left=backtrack(preIndex+1,inStart,inIndex-1,preorder,inorder); root.right=backtrack(preIndex+1+inIndex-inStart,inIndex+1,inEnd,preorder,inorder); return root; }
105. Construct Binary Tree from Preorder and Inorder Traversal（js）
原文：https://www.cnblogs.com/xingguozhiming/p/10713111.html