2023年6月22日发(作者：)

[JS]前序遍历和中序遍历的结果还原⼀棵⼆叉树，很经典的问题/** * 前序遍历和中序遍历的结果还原⼀棵⼆叉树，很经典的问题 */function TreeNode(val) { = val; = = null;}/** * 根据前序和中序的结果还原⼆叉树 * @param {*} pre 前序遍历的序列 * @param {*} vin 中序遍历的序列 */function buildTree(pre, vin){ // ('=======start=========') if( == 0 || == 0){ return null } // 1)根据前序遍历的第⼀个节点就是原⼆叉树的根节点，求得根节点是 1 var index = f(pre[0]); //获取根结点索引

// 2)根据中序遍历，根节点左边就是左⼦树的节点，求得左树的范围 [4,7,2] var leftTree = (0, index); //左树的范围

var rightTree = (index+1); //右树的范围

//新建⼆叉树 var node = new TreeNode(vin[index]) //根节点以及后续迭代的各节点 = buildTree((1, index+1), leftTree) = buildTree((index+1), rightTree);

return node;}//测试⽤例// buildTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6])('最终还原的⼆叉树为：',buildTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]))最终还原的⼆叉树为： TreeNode {val: 1,right: TreeNode {val: 3,right: TreeNode { val: 6, right: null, left: [TreeNode] },left: TreeNode { val: 5, right: null, left: null }},left: TreeNode {val: 2,right: null,left: TreeNode { val: 4, right: [TreeNode], left: null }}}