开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

从inorder和preorder遍历重构二叉树

从inorder和preorder遍历重构二叉树是一个常见的编程问题，可以使用递归或迭代的方法来解决。这里我们给出一个使用递归方法的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)

这个函数接受两个列表作为参数，分别是preorder和inorder遍历的结果。首先，我们找到根节点的值，然后在inorder遍历中找到根节点的位置，从而确定左子树和右子树的inorder遍历结果。接着，我们根据左子树和右子树的inorder遍历结果，在preorder遍历中找到对应的子树，并递归地构建左子树和右子树。最后，返回根节点。

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

相关搜索:二叉树的生成、遍历和打印从Gremlin中的1次遍历返回一个'graphml‘子图和一个集合从保存的配置和权重构建时，tf.keras.layers.TextVectorization存在一个错误使用“表达式树”自动将“inorder/infix”表达式转换为相应的“PostOrder”和“PreOrder”表达式使用中序和预序遍历生成二叉树具有搜索和删除功能的python二叉树遍历如何检查给定的preorder、inorder和postorder遍历是否属于相同的二叉树？将inorder代码转换为preorder和postorder 我的代码中出现了一个错误。问题:从预序和中序遍历构造二叉树无法正确遍历二叉树以检索提取到字符串的所有LeftChild和RightChild

相关搜索:

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

有帮助

没帮助

相关·内容

重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...: [-1] 限制： 0 <= 节点个数 <= 5000 思考我们知道，前序和中序的遍历特点：前序：根、左子树、右子树中序：左子树、根、右子树所以，当给定前序和中序的遍历结果，如：（前序）preorder...= [3,9,20,15,7], （中序）inorder = [9,3,15,20,7] 那么，我们可以很容易确定： 1、根节点的值为preorder[0] 2、在中序遍历结果中可以找到根节点的位置，...= i break; } } 3、有了rootIndex，通过中序遍历结果就可以知道左 / 右子树的内容，假如拷贝一份的话，左子树和右子树中序遍历为： 4、左子树的个数为...另外，本文是通过前序和中序来实现二叉树的重构，如果遇到后序列和中序来重建二叉树，也是一样的思考方式。只不过后序的跟节点是最后一个。

1971 0

☆打卡算法☆LeetCode 105、从前序与中序遍历序列构造二叉树算法解析

一、题目 1、算法题目 “给定两个整数数组pre和ino，其中pre是二叉树的先序遍历，ino是二叉树的中序遍历，构造二叉树返回其根节点。”...从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com) 2、题目描述给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历...， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。...= [-1], inorder = [-1] 输出: [-1] 二、解题 1、思路分析真是不停的被二叉树折磨，这道题是由两个整数数组，一个先序遍历一个中序遍历，构造出二叉树返回根节点。...」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left +

2323 0

PAT 1020 Tree Traversals (25分) 解读

Sample Input: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 Sample Output: 4 1 6 3 5 7 2 ==说白了就是，给你一棵二叉树的后序遍历结果和中序遍历结果...== 题解：我们应该都接触过由中序遍历和先序遍历得到后序遍历，或者由中序遍历和后序遍历得到先序遍历，其实只要你根据给出的两个序列重构出这棵二叉树，层序遍历也就得到了。...但重构二叉树需要自己创建二叉树的数据结构，还要造一棵树出来，其中指针操作又容易出错，我不想创建树可以吗？可以的！...题目只是让我输出最后的遍历结果，又不是让我得到一棵树，我只需要巧妙的调整一下代码就能利用一个map得到层序遍历的结果（柳婼大神nb）但不管怎么样，都得先解决一个问题，就是利用中序序列和后序序列怎么得到二叉树呢...i = 0; i > inorder[i]; // 得到层序 Preorder(0, n - 1, n - 1, 0); // 遍历，注意输出格式

4943 0

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

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

1162 0

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20...* 先根据先序遍历确认根节点，然后找出根节点在中序遍历的位置，从而确定左子树的长度和右子树的长度，对应到先序遍历中也能找出对应的左子树和右子树， * 分别递归左子树和右子树，重复上面步骤。...//递归的构造左子树，并连接到根节点 //先序遍历中【从左边界+1 开始的size_left_subtree】个元素就对应了中序遍历中【从左边界开始到根节点定位-1】的元素...的元素对应了中序遍历中【从左边界开始到根节点-1】的元素 root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree

1343 0

Leetcode No.105 从前序与中序遍历序列构造二叉树

一、题目描述根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20...这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。..., inorder_left, inorder_root - 1); // 递归地构造右子树，并连接到根节点 // 先序遍历中「从左边界+1+左子树节点数目开始到右边界...」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root->right = myBuildTree(preorder, inorder, preorder_left

1941 0

给出前序遍历和中序遍历求二叉树_已知前序遍历和后序遍历

，能够创建出一棵唯一的二叉树，可以得出二叉树的后序遍历； 2.已知后序遍历，中序遍历序列，能够创建出一棵唯一的二叉树，进而可以得出二叉树的先序序列； 3.综上，必须含有中序遍历(确定二叉树左右孩子)，先序遍历或者后序遍历任选一个...(确定二叉树父子结点)，就可以确定一棵唯一的二叉树 三、C++代码实现 1.已知先序遍历和中序遍历，打印后序遍历（见函数void postorder(string preorder, string inorder...)）； 2.已知中序遍历和后序遍历，打印先序遍历（见函数void preorder(string inorder, string postorder)）； #include #include...(pos+1,len-pos-1), inorder.substr(pos+1,len-pos-1));//后序遍历右子树，pos从0开始，所以len-pos-1 cout<<preorder[0]...]; preorder(inorder.substr(0, pos), postorder.substr(0, pos)); //先序遍历左子树 preorder(inorder.substr

5712 0

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

4379 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 是同一棵树的后序遍历，请你构造并返回这颗二叉树...[i] == postorder[pos]) break; i++; } pos--;//从后往前遍历

2232 0

Python算法——树的重建

Python中的树的重建算法详解树的重建（Tree Reconstruction）是一种从给定的遍历序列中恢复原树结构的算法。...在本文中，我们将讨论树的重建问题以及常见的重建算法，包括先序遍历和中序遍历序列重建二叉树，以及层序遍历序列重建二叉树。我们将提供Python代码实现，并详细说明每个算法的原理和步骤。 1....先序遍历和中序遍历序列重建二叉树 给定一个二叉树的先序遍历序列和中序遍历序列，我们可以通过递归地进行树的重建。...current.right = TreeNode(right_val) queue.append(current.right) return root 示例示例1：先序遍历和中序遍历序列重建二叉树...Reconstructed Tree from Level Order: 9 3 15 20 7 以上两个示例演示了树的重建算法的使用，分别使用先序遍历和中序遍历序列，以及层序遍历序列重建二叉树。

1801 0

算法：分治

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。...基于中序遍历的左子树，能够从后续遍历中找到左子树的后续遍历；基于中序遍历的右子树，能够从后续遍历中找到右子树的后续遍历；问题分解成了两个小的问题，方法一样，采用分治递归的思想解决，这里有个小技巧就是使用哈希表存储元素映射位置...给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。...保证为二叉树的前序遍历序列 inorder 保证为二叉树的中序遍历序列解题思路：与之前的中序遍历和后续遍历一样，先找到根节点，然后将其分为左子树和右子树，分治递归的构建左子树和右子树前序遍历的顺序...」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root->right = myBuildTree(preorder, inorder, preorder_left

1K3 0

C++【二叉树进阶试题】

：在二叉树中序遍历的基础之上，传递指向当前节点的指针和指向上一个节点的指针，在两者之间建立链接关系，当中序遍历结束后，双向链表就转换完成了为什么是 prev 的 right 链接 cur ？...从前序与中序遍历序列构造二叉树 题目分析：给定一个前序和中序遍历，还原出二叉树，前序【根左右】、中序【左根右】，因此前序序列中的第一个节点一定是整个二叉树的根解题思路：传递前序和中序序列，根据前序序列中的节点...从前序与中序遍历序列构造二叉树 //https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal...从中序与后序遍历序列构造二叉树 题目分析：前序、中序可以重构二叉树，中序、后序同样也可以，因为后序一样可以确认根，然后一样从中序序列中划分区间解题思路：反向遍历后序序列，创建根节点，从中序序列中划分出左右区间..., 0, inorder.size(), postorder, pos); return root; } }; 注意：中序、后序重构二叉树时，需要先链接右子树，再链接左子树

2401 0

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

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

3783 0

为实习准备的数据结构（4）-- 二叉树

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。...」的元素就对应了中序遍历中「从根节点定位+1 到右边界」的元素 root->right = myBuildTree(preorder, inorder, preorder_left...这样以来，我们就知道了左子树的后序遍历和中序遍历结果，以及右子树的后序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。...} }; --------- 二叉树的层序遍历所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下： [在这里插入图片描述] 实现步骤： 1.创建队列，存储每一层的结点...所以在二叉树中找到最大值和最小值是很简单的，比较麻烦的是元素的插入和移除。插入新元素时，从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到尾端，即为插入点。

3671 0

重建二叉树（Java）

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。...父结点和子结点之间用指针链接。 二叉树：二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。在二叉树中最重要的操作是遍历，即按照某一顺序访问树中的所有结点。...解题思路：题目中给了我们先序遍历和中序遍历；在二叉树的前序遍历中，第一个数字总是树的根结点的值。...(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); return root; } // 构建二叉树的核心算法...(preorder, inorder); System.out.println(treeNode); } 举一反三：类似的由中序和后序构建二叉树和有前序和中序构建二叉树的思想是类似的。

2591 0

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

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

4874 0

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

从前序与中序遍历序列构造二叉树 力扣题目链接[1] 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点...<= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder...均「无重复」元素 inorder 均出现在 preorder preorder 「保证」为二叉树的前序遍历序列 inorder 「保证」为二叉树的中序遍历序列思路：本题考查前序和中序遍历的特点...preorder.length) return null; // 二叉树为空 const root = preorder[0]; // 从前序遍历获取根节点 const node = new..., inRight); // 递归构造右子树 return node; // 返回构造出的节点 }; 总结本题需要结合前序遍历和中序遍历，来将二叉树拆分为左子树、根、右子树三个部分。

2272 0

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

作者：TeddyZhang，公众号：算法工程师之路 1 编程题 二叉树拓展到N叉树思路先序中入栈顺序先右后左 --> 孩子节点数组从右向左入栈后序中入栈顺序先左后右 --> 孩子节点数组从左向右入栈...根据一棵树的前序遍历与中序遍历构造二叉树。...例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： ?...【LeetCode #106】从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。...例如，给出中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树： ?

1.2K2 0

根据先序和中序输出后序遍历

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入描述: 两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。...否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。简单来说中序遍历就是从左子树返回时遇到结点就访问。 3.后序遍历的递归过程为：若二叉树为空，遍历结束。...否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树；③访问根结点。简单来说后序遍历就是从右子树返回时遇到结点就访问。...根据先序和中序求后序 { int n = preorder.length(); //n为每次遍历数目 if(n > 0) { char root = preorder...cout << root; } } int main() { string preorder,inorder; //先序遍历和中序遍历 while(cin >> preorder

2.2K2 0

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

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

1692 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭