从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是二叉树中节点的数量。
相关·内容
1回答
我试图遍历由键盘输入数据构建的二叉树。数据已成功插入到二叉树中。我有一个开关语句，其中'case 2‘应该使用递归遍历(和打印)二叉树，分别使用顺序遍历算法、前置遍历算法和后置遍历算法。；{
{
inorder((*TemPtr).l
浏览 3提问于2016-01-10得票数 0
回答已采纳
1回答
给定两个整数数组的序号和序号，其中序号是二叉树的序遍历，无序是同一树的序遍历，构造并返回二叉树。
preorder_queue= deque(preorder)
def helper(pr
浏览 3提问于2022-07-30得票数 1
1回答
给定树的前序和中序遍历，构造二叉树。例如: preorder = 3,9,20,15,7 inorder = 9,3,15,20,7 返回二叉树。我的代码如下： //helper function
TreeNode* build(vector<int> &preorder, vector<int> &inorder, int start, int(),inorder.end(
浏览 17提问于2020-09-12得票数 0
回答已采纳
1回答
从顺序遍历和后置遍历迭代构造二叉树。我为无序和预排序编写了一个算法，但是我想知道如何修改它以适应顺序和后置顺序？注意:它是伪码，"=“的意思是"==”e: TElementleft: PNode (pointer to a Node)
浏览 1提问于2021-06-28得票数 1
回答已采纳
1回答
init__(self,data): self.right = None if root: print (root.data) if root:
print (root.dat
浏览 0提问于2020-05-16得票数 0
1回答
在构造二叉树时处理重复项
、、、、
leetcode中遇到了以下问题-https://leetcode.com/problems/serialize-and-deserialize-binary-tree/ 我能够在下面编写一个算法(找到前序和后序遍历并保存它们然后从遍历重建树)，但达到了一个更基本的问题-即，如何构建具有重复值的二叉树。我失败的测试用例是3,2,4,3其中预订单和后订单是相同的。 感谢任何帮助和建议。= inOrder(
浏览 50提问于2021-02-24得票数 2
回答已采纳
2回答
我尝试在它的前序和中序遍历上构建一个二叉树条件。vector<int> inorder_left(inorder.begin(), inorder.begin() + getIndex(inorder, preorder.front()));vector<int> inorder_right(inorder.begin() + getIndex(inorder, pr
浏览 0提问于2017-11-08得票数 0
1回答
我有一个关于二叉树遍历代码是如何工作的问题。void BinaryTree_Functions::preorder(Binary_TreeNode* bt) if (bt == NULL) { return; }cout << bt->data <<endl; preorder(bt->Right);前置遍历
void<em
浏览 3提问于2022-03-02得票数 -4
回答已采纳
2回答
我们知道，给定的二叉树的预序和中序遍历唯一地定义了树，那么一般的树，即具有两个以上子树的树，预序和中序遍历是否与树结构一一对应。换句话说，给定一个普通树的元组( preorder，inorder)，它对于一个普通树来说是唯一的，还是可以有许多树具有相同的preorder和inorder遍历元组？
浏览 2提问于2014-07-01得票数 3
4回答
我正在读的一本书声称，检查二叉树B是否为二叉树A的子树的一种方法是构建两棵树的inorder和preorder字符串(表示每棵树的顺序遍历和前置遍历的字符串)，并检查inorder_B是否为inorder_A的子字符串， preorder_B是否为preorder_A的子字符串。请注意，它要求您必须检查上的子字符串匹配，、无序和预定字符串。
是否真的有必要在上检查
浏览 5提问于2013-01-11得票数 7
回答已采纳
1回答
我定义了自己的数据类型BinTree，它描述了我的二叉树： data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show,Eq) 之后，我为二叉树实现了三个排序函数：preorder、inorder和postorder preorder :: BinTree a -> [a]preorder(Node x lt rt) = [
浏览 17提问于2021-01-31得票数 2
我读到前序和后序遍历也是为一般的(n元)树定义的，如下所示： if(v==null) return; for each child w of vpreOrder(w)
if(v==null) return; postOrder(w)
print(v)但中序遍历仅适用于二叉树。为什么我不能像上面展示的pre和postOrder
浏览 5提问于2021-04-07得票数 1
2回答
二叉树可以用两个谓词来定义：
如果inorder(T,L)是由二叉树T的无序遍历生成的节点列表，则L为真。如果postorder(T,L)是二叉树</em
浏览 6提问于2013-07-30得票数 2
回答已采纳
当使用递归方法以/pre/post顺序遍历二叉树时，我目前正在尝试获得二叉树节点的正确排序。我所能找到的唯一解决方案是使用一个全局变量来保存每种遍历类型的列表。= key
inList = []postList = []
def inorder(root): inorder(root.left)
浏览 1提问于2018-11-03得票数 0
基本上，它应该从inOrder和preOrder遍历数据(作为整数数组发送进来)重建二叉树--它是整数的二叉树。这是我用的树： / \ / \ \preOrder是234，98，45,124,678,1789 inOrder我决定在inOrder数组中切换678和1789，这使得17
浏览 2提问于2013-04-08得票数 1
给定树的前序和中序遍历，构造二叉树。 注意:您可以假设树中不存在重复项。 /** } root
浏览 11提问于2020-09-24得票数 0
回答已采纳
在下面的程序中，一个助手函数被递归地调用，以便从由数组表示的前置和后置遍历创建一个二叉树。运行时速度快，比所有提交的Leetcode的100%都要好。TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
浏览 0提问于2019-02-11得票数 1
回答已采纳
1回答
不知何故，我设法编写了一个算法，用于从二叉树的无序和前置遍历数据中构建二叉树。 public static void main(String[] args) { int[] inOrder = new int[] { 2, 1
浏览 2提问于2012-07-02得票数 1
(Python 2.7)我需要打印具有给定的preorder和inorder的二叉树的bfs，以及preorder和inorder字符串的最大长度。我知道它是如何工作的，例如: preorder:ABCDE inorder:CBDAE max length:5 / \print"insert the inorder"
浏览 0提问于2012-06-24得票数 3
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
云直播
对象存储活动推荐
腾讯云开发者
