百度站长怎么做网站维护,中国深圳航空公司官网,医疗类网站还有做seo,汽车交易网站系统建设文章目录 从前序与中序遍历序列构造二叉树我的思路网上思路 总结 从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 示… 文章目录 从前序与中序遍历序列构造二叉树我的思路网上思路 总结 从前序与中序遍历序列构造二叉树 给定两个整数数组 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);
}讲解 先序遍历先序遍历的顺序是根节点 - 左子树 - 右子树。这意味着先序遍历的第一个元素总是树的根节点。中序遍历中序遍历的顺序是左子树 - 根节点 - 右子树。通过中序遍历可以明确知道根节点在哪些元素的左侧哪些元素的右侧从而区分左右子树。递归构建知道了根节点就可以在中序遍历中找到根节点的位置这个位置将中序序列分成两部分左边是左子树的中序遍历右边是右子树的中序遍历。同时根据先序遍历中根节点之后的元素个数可以确定左右子树的先序遍历范围。然后递归地在左右子树的先序和中序序列中构建子树。 网上思路
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;
}讲解 首先检查 preorder 和 inorder 数组是否为空。创建根节点并将其入栈。遍历 preorder 数组从第二个元素开始。对于每个新节点检查栈顶元素是否与当前 inorder 中的值相同如果相同则弹出栈顶元素并继续检查直到栈顶元素与 inorder 中的值不同。如果不同则将新节点作为栈顶元素的左子节点。最后将新节点入栈。 总结
现在看来栈也是一个好的解题思路明天可以试试
