开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

如何从preorder和inorder遍历构建二叉树

从preorder和inorder遍历构建二叉树是一个常见的编程问题。以下是一个使用Python实现的解决方案：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root_index = inorder.index(root_val)
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]
    left_preorder = preorder[1:1+len(left_inorder)]
    right_preorder = preorder[1+len(left_inorder):]
    left_tree = buildTree(left_preorder, left_inorder)
    right_tree = buildTree(right_preorder, right_inorder)
    return TreeNode(root_val, left_tree, right_tree)

这个解决方案首先定义了一个TreeNode类，用于表示二叉树的节点。然后，定义了一个buildTree函数，该函数接受两个列表作为参数：preorder和inorder。preorder列表表示前序遍历，inorder列表表示中序遍历。

函数首先检查preorder和inorder列表是否为空，如果为空，则返回None。接下来，根据preorder列表的第一个元素（即根节点的值）找到inorder列表中的根节点位置。然后，将inorder列表分为左子树和右子树的列表，以及preorder列表分为左子树和右子树的前序遍历列表。

接下来，递归地调用buildTree函数，分别使用左子树的前序遍历和中序遍历列表以及右子树的前序遍历和中序遍历列表来构建左子树和右子树。最后，返回一个新的TreeNode实例，其中包含根节点的值、左子树和右子树。

这个解决方案的时间复杂度为O(n)，其中n是二叉树中节点的数量。

相关搜索:从inorder和preorder遍历重构二叉树如何检查给定的preorder、inorder和postorder遍历是否属于相同的二叉树？问题的解决方案超时:从inorder和postorder构建二叉树如何从字符串表达式构建二叉树如何从构建中排除vuetify和vue？如何从外部脚本访问Xcode环境(和构建)变量？如何从jenkins上传maven包和构建信息到artifactory 我的代码中出现了一个错误。问题:从预序和中序遍历构造二叉树如何从obj文件中获取运行库和构建类型？如何使用Cobrix从带有COMP字段的cobol和ebcdic文件构建数据帧？关于从哪里获得如何构建BI和Crystal报表的基本理解的建议？如何构建Restful API，从Rails到Hubspot Forms API和/或修改嵌入式代码？如何从具有组(节点)和值(边)的数据帧构建网络可视化？如果不下载SDK和XCODE，我如何在在线平台上从ember应用构建android和ios应用？如何从训练数据和预期结果列表中创建tensorflow数据库，以及如何构建独特的网络形状如何从控制台xcodebuild构建中创建用于over- the -air的IPA和manifest.plist 如何在运行时从泛型类型定义和运行时类型参数构建Java类型对象？如何使用pandas、python和ta-lib从多个csv构建数据帧，从而按顺序计算技术指标如何从x86_64和arm arch的源代码构建docker-compose容器？(提交前请提供带`from`的源镜像)

相关搜索:

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

LeetCode：105_Construct Binary Tree from Preorder and Inorder Traversal | 根据前序和中序遍历构建二叉树 | Medium

要求：通过二叉树的前序和中序遍历序列构建一颗二叉树 代码如下： 1 struct TreeNode { 2 int val; 3 TreeNode *left...right(NULL) {} 6 }; 7 8 typedef vector::iterator Iter; 9 TreeNode *buildTree(vector &preorder..., vector &inorder) 10 { 11 return buildTreeRecur(preorder.begin(), preorder.end(), inorder.begin...(), inorder.end()); 12 } 13 14 TreeNode *buildTreeRecur(Iter pstart, Iter pend, Iter istart, Iter iend

4389 0

【算法】重建二叉树并进行后序遍历的Java实现

后序遍历代码实现代码解释总结在二叉树的问题中，给定二叉树的前序遍历（Preorder）和中序遍历（Inorder）序列，如何求得其后序遍历（Postorder）序列是一个经典的面试题。...本文将详细介绍如何通过Java实现这一过程。问题描述前序遍历（Preorder）：按根节点 -> 左子树 -> 右子树的顺序访问节点。...给定前序遍历和中序遍历序列，我们需要构建二叉树并输出其后序遍历序列。实现思路重建二叉树：利用前序遍历和中序遍历的特性，通过递归方法重建二叉树。...在中序遍历中找到该根节点的位置，可以将中序遍历数组分为左子树和右子树两部分。递归地对这两部分继续构建左右子树。 2....buildTree 方法：接受前序遍历和中序遍历数组，构建并返回二叉树的根节点。 buildTreeHelper 方法：递归地构建二叉树。

1131 0

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

题目根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 /...\ 15 7 题解根据前序和中序可以构造一颗二叉树，根据中序和后续也可以构建一颗二叉树。...反正必须要有中序才能构建，因为没有中序，你没办法确定树的形状。比如先序和后序是不能构建唯一的一颗二叉树的。...那回到这个题目, 其实思路比较好想到，就是如何划分子问题，然后递归的构建左子树和右子树。

8471 0

手把手教你如何重建二叉树（超精彩配图）

一、二叉树的重建在LeetCode中有这么一道算法题：《重建二叉树》（一）面试题07. 重建二叉树 面试题07. 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。...\ 15 7 限制： 0 <= 节点个数 <= 5000 （二）分析该题目从题目中可以看到，给出了两个数组，一个书前序遍历二叉树得出的结果，一个是中序遍历二叉树得出的结果。...利用这两个结果，来还原出一颗二叉树。首先你要知道什么是前序遍历和中序遍历。你还要知道，给你一颗二叉树，使用这些遍历的算法怎么得到遍历的结果，不然是没办法继续完成重建二叉树的。...*/ public class Solution { /** * 根据前序和中序遍历的二叉树的结果构建二叉树 * @param preorder 前序遍历结果的数组.../** * 根据前序和中序遍历的二叉树的结果构建二叉树 * @param preorder 前序遍历结果的数组 * @param inorder 中序遍历结果的数组

3793 0

重建二叉树（Java）

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。...解题思路：题目中给了我们先序遍历和中序遍历；在二叉树的前序遍历中，第一个数字总是树的根结点的值。...我们已经分别找到了左右子树的前序和中序遍历，我们可以用同样的方法分别去构建左右子树，即递归实现。...(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); return root; } // 构建二叉树的核心算法...(preorder, inorder); System.out.println(treeNode); } 举一反三：类似的由中序和后序构建二叉树和有前序和中序构建二叉树的思想是类似的。

2611 0

LeetCode——遍历序列构造二叉树

105从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点...preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均无重复元素 inorder 均出现在 preorder...preorder 保证为二叉树的前序遍历序列 inorder 保证为二叉树的中序遍历序列原题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal...106从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树...) break; i++; } pos--;//从后往前遍历 root->right = section

2252 0

剑指Offer面试题：5.重建二叉树

一、题目：重建二叉树 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示的二叉树并输出它的头结点。　 ?...在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值的步骤如下图所示：　　分别找到了左、右子树的前序遍历序列和中序遍历序列，我们就可以用同样的方法分别去构建左右子树。...在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后，就可以递归地去分别构建它的左右子树。...; } } 　　该方法首先接收参数，依次打印先序遍历和中序遍历，最后通过调用Construct方法获得重建的二叉树的根节点，并实例化一个二叉树的数据结构（本处的二叉树结构的实现请阅读

4884 0

N叉树问题-LeetCode 429、589、590、105、106（构建二叉树，N叉树遍历）

作者：TeddyZhang，公众号：算法工程师之路 1 编程题 二叉树拓展到N叉树思路先序中入栈顺序先右后左 --> 孩子节点数组从右向左入栈后序中入栈顺序先左后右 --> 孩子节点数组从左向右入栈...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： ?...同理得到右子树的前序和中序遍历，那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树，即得到答案！ /** * Definition for a binary tree node....【LeetCode #106】从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。...同理得到右子树的后序和中序遍历，那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树，即得到答案！ /** * Definition for a binary tree node.

1.2K2 0

Python算法——树的重建

Python中的树的重建算法详解树的重建（Tree Reconstruction）是一种从给定的遍历序列中恢复原树结构的算法。...在本文中，我们将讨论树的重建问题以及常见的重建算法，包括先序遍历和中序遍历序列重建二叉树，以及层序遍历序列重建二叉树。我们将提供Python代码实现，并详细说明每个算法的原理和步骤。 1....先序遍历和中序遍历序列重建二叉树 给定一个二叉树的先序遍历序列和中序遍历序列，我们可以通过递归地进行树的重建。...层序遍历序列重建二叉树 给定一个二叉树的层序遍历序列，我们可以使用队列来逐层构建树结构。队列中的每个元素代表一个树节点，我们按照层序遍历的顺序依次将节点加入队列，并根据队列中的顺序建立树的连接关系。...Reconstructed Tree from Level Order: 9 3 15 20 7 以上两个示例演示了树的重建算法的使用，分别使用先序遍历和中序遍历序列，以及层序遍历序列重建二叉树。

1811 0

通过前序+中序和后序+中序来构建二叉树

在这里插入图片描述前序 + 中序题意：给你一个前序遍历和中序遍历，你要构造出一个二叉树。...示例：前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 要想解决这类题目，我们就要掌握遍历的特点。...我们能找到根节点，就能找到左子树和右子树的集合，那么这个二叉树是不是就已经有了一个大致的样子。接下来要做的，就是使用递归去构建出左子树和右子树。示例过程： ? 1 ? 2 ?...找到根结点（后序遍历的最后一位）在中序遍历中，找到根结点的位置，划分左右子树，递归构建二叉树。这里希望各位自行在草稿纸上画一下，二叉树构建过程。...二叉树的问题绝大部分都是和三种遍历有关，思考问题的时候，可以从三种遍历的特点入手。

2.4K3 0

重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...: [-1] 限制： 0 <= 节点个数 <= 5000 思考我们知道，前序和中序的遍历特点：前序：根、左子树、右子树中序：左子树、根、右子树所以，当给定前序和中序的遍历结果，如：（前序）preorder...rootIndex - 0 = rootIndex, 所以也能通过前序遍历的结果知道前序左 / 右子树内容，假如拷贝一份的话，左子树和右子树前序遍历为： 5、然后通过递归，继续构造左 / 右子树就可以完成树的构建...(preorder[0]); } /** * 超过1个节点，递归调用构建 */ return this.buildByRecur(preorder, 0,...另外，本文是通过前序和中序来实现二叉树的重构，如果遇到后序列和中序来重建二叉树，也是一样的思考方式。只不过后序的跟节点是最后一个。

1981 0

每日一题：LeetCode-105.从前序遍历与中序遍历构造二叉树

✈️✈️ LeetCode-105.从前序与中序遍历序列构成二叉树：题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历...inorder[i] <= 3000 preorder 和 inorder 均无重复元素 inorder 均出现在 preorder preorder 保证为二叉树的前序遍历序列 inorder...保证为二叉树的中序遍历序列解法：思路：我们在学习二叉树的时候，很早就会了使用前序和中序或者中序和后序的序列来还原一颗二叉树。...接着向左子树和右子树分别重复上述操作，就可以递归构建一颗二叉树、 1、我们把前序遍历数组的左右子树给找出来，所以需要中序遍历的结果来，用pos作为下标，只要中序遍历数组的值不等于前序遍历数组的第一个值...right = buildTree(preArr, inArr); return root; } }; 这是一道力扣的中等题，总的来说也并不算很难，理解掌握对前序遍历与中序遍历递归构建的过程才是最重要的

1031 0

构建二叉树

从中序与后序构建二叉树 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。...不为空则向下继续，为空返回null 去后序数组中的最后一个元素为树的头节点的val值，（原因由后序遍历可知）切割中序数组，以头节点的val值为区分（作为切割点），切割成中序左数组和中序右数组...思路与从中序和后序构建二叉树相同代码实现 class Solution { Map map; // 方便根据数值查找位置 public TreeNode.../** * 通过中序数组 and 后序数组构建一颗二叉树 * @param inorder 中序数组 * @param postorder 后序数组 * @return */ Node*...buildTree(leftIn, leftPost); root->right = buildTree(rightIn , rightPost); return root; } 从前序与中序构建二叉树

621 0

【算法题解】 Day30 搜索与回溯

二叉树中和为某一值的路径难度：medium 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。...重建二叉树 题目剑指 Offer 07. 重建二叉树 难度：medium 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。...这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。..., inorder_left, inorder_root - 1) # 递归地构造右子树，并连接到根节点 # 先序遍历中「从左边界+1+左子树节点数目...」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left +

1162 0

剑指Offer题解 - Day44

重建二叉树 力扣题目链接[1] 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...Input: preorder = [-1], inorder = [-1] Output: [-1] 限制： 0 <= 节点个数 <= 5000 思路：本题是通过先序遍历和中序遍历的结果来倒推二叉树的结构...知道了左子树的数量和右子树的数量，此时就可以将前序遍历的数组分为[根节点|左子树|右子树] 也就是说，「中序遍历是为了明确在前序遍历里如何分割左子树和右子树」。...= (preorder, inorder) => { let map = new Map(); // 初始化哈希表，存储中序遍历的值与索引对应关系 for (let i = 0; i...本题也比较复杂，需要多思考如何通过前序和中序遍历来构建二叉树。

1572 0

剑指offer | 面试题6：重建二叉树

blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_06_buildTree/Solution.java 题目描述：输入某二叉树的前序遍历和中序遍历的结果...，请构建该二叉树并返回其根节点。...假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...」个元素就对应了中序遍历中「从左边界开始到根节点定位-1」的元素 root.left = myBuildTree(preorder, inorder, preorder_left +...// 先序遍历中「从左边界+1+左子树节点数目开始到右边界」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root.right = myBuildTree(preorder

1702 0

剑指 Offer（C++版本）系列：剑指 Offer 07 重建二叉树

剑指 Offer（C++版本）系列：剑指 Offer 07 重建二叉树 1、题干重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。...假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20...); 构建左右子树：开启左右子树递归；前序遍历左边界前序遍历右边界中序遍历左边界中序遍历右边界左子树 pl + 1 pl + 1 + len il k - 1 右子树 pl + 1 + len..., vector& inorder) { int n = preorder.size(); for (int i = 0; i<n; ++i) pos[inorder[i]] = i;

2722 0

——二叉树链式结构的实现

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。 2. 二叉树的遍历 1. 前序、中序以及后序遍历学习二叉树结构，最简单的方式就是遍历。...NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。...// 二叉树前序遍历 void PreOrder(TreeNode* root); // 二叉树中序遍历 void InOrder(TreeNode* root); // 二叉树后序遍历 void PostOrder...("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } 2.中序遍历递归 InOrder函数实现了二叉树的中序遍历。...// 二叉树前序遍历 void PreOrder(TreeNode* root); // 二叉树中序遍历 void InOrder(TreeNode* root); // 二叉树后序遍历 void PostOrder

711 0

二叉树经典OJ题（2）

四、前序和中序遍历序列构建二叉树 . - 力扣（LeetCode） class Solution { public: TreeNode* _buildTree(vector& preorder...preorder,inorder,pi,begin,rooti-1); root->right=_buildTree(preorder,inorder,pi,rooti+1,end);...int pi=0;//帮助我们按顺序遍历前序数组 return _buildTree(preorder,inorder,pi,0,inorder.size()-1);...} }; 五、中序和后序序列遍历构建二叉树 . - 力扣（LeetCode） class Solution { public: TreeNode* _buildTree(vector&...2、前序和中序构建二叉树，以及中序和后序构建二叉树，本质上是利用一个序列找根，另一个序列去划分问题。

591 0

常考算法面试题系列：树的遍历

根据根节点，左孩子节点和右孩子节点的访问顺序又可以将 DFS 细分为先序遍历 preorder，中序遍历 inorder 和后序遍历 postorder。...postorder[postorder.length - 1]); // 根据左子树的中序和后序遍历构建左子树 treeNode.left = buildTree(inorder.slice...(0, i), postorder.slice(0, i)); // 根据右子树的中序和后序遍历构建右子树 treeNode.right = buildTree(inorder.slice...// 根据左子树的前序和中序遍历构建左子树 treeNode.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));...// 根据右子树的前序和中序遍历构建右子树 treeNode.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));

7053 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭