学习记录：js算法（五十六）：从前序与中序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

我的思路
递归
网上思路
栈

我的思路

var buildTree = function (preorder, inorder) {const build = (preStart, inStart, inEnd) => {if (inStart > inEnd) return null; // 终止条件：没有节点要构建了// 先序遍历中的第一个节点就是当前子树的根节点const rootVal = preorder[preStart];const root = new TreeNode(rootVal);// 在中序遍历中找到根节点的位置，以此划分左右子树const index = inorder.indexOf(rootVal, inStart, inEnd + 1);// 递归构建左子树和右子树root.left = build(preStart + 1, inStart, index - 1);root.right = build(preStart + index - inStart + 1, index + 1, inEnd);return root;};return build(0, 0, inorder.length - 1);
}

讲解

1. 先序遍历：先序遍历的顺序是根节点 -> 左子树 -> 右子树。这意味着先序遍历的第一个元素总是树的根节点。
2. 中序遍历：中序遍历的顺序是左子树 -> 根节点 -> 右子树。通过中序遍历，可以明确知道根节点在哪些元素的左侧，哪些元素的右侧，从而区分左右子树。
3. 递归构建：知道了根节点，就可以在中序遍历中找到根节点的位置，这个位置将中序序列分成两部分，左边是左子树的中序遍历，右边是右子树的中序遍历。同时，根据先序遍历中根节点之后的元素个数，可以确定左右子树的先序遍历范围。然后递归地在左右子树的先序和中序序列中构建子树。

网上思路

var buildTree = function (preorder, inorder) {if (preorder.length === 0 || inorder.length === 0) {return null;}const root = new TreeNode(preorder[0]);const stack = [root];let inorderIndex = 0;for (let i = 1; i < preorder.length; i++) {const node = new TreeNode(preorder[i]);// 将栈顶元素与当前节点进行连接let topNode = stack[stack.length - 1];// 如果栈顶元素的值与中序遍历的当前值相同，则说明当前节点是栈顶元素的右子节点if (topNode.val === inorder[inorderIndex]) {while (stack.length > 0 && stack[stack.length - 1].val === inorder[inorderIndex]) {topNode = stack.pop();inorderIndex++;}topNode.right = node; // 连接到右子节点} else {topNode.left = node; // 连接到左子节点}// 将当前节点入栈stack.push(node);}return root;
}

讲解

1. 首先检查 preorder 和 inorder 数组是否为空。
2. 创建根节点并将其入栈。
3. 遍历 preorder 数组，从第二个元素开始。
4. 对于每个新节点，检查栈顶元素是否与当前 inorder 中的值相同：
5. 如果相同，则弹出栈顶元素，并继续检查，直到栈顶元素与 inorder 中的值不同。
6. 如果不同，则将新节点作为栈顶元素的左子节点。
7. 最后，将新节点入栈。

总结

现在看来，栈也是一个好的解题思路，明天可以试试