308 字
2 分钟
算法之重建二叉树
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
解法：
1.递归
思路：
递归，六句代码包含着大智慧。 首先我们要明白前序遍历和中序遍历的节点遍历顺序。 前序遍历：根->左->右 中序遍历：左->根->右 结合题目的数组我们可以得到一个信息： preorder得到的根节点，在inorder中的它的位置，左侧是左子树，右侧是右子树 而在inorder获取的索引可以帮助我们划分preorder数组 于是我们可以通过划分数组的方式递归得到叶子节点， 然后通过一步步的回溯把它们组装起来，就是一棵完整的树
/** * 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) { if (preorder.length === 0) return null const cur = new TreeNode(preorder[0]) const index = inorder.indexOf(preorder[0]) cur.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index)) cur.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1)) return cur};