根据后序和中序遍历求先序遍历
来源 :华课网校 2024-09-05 22:39:43
中二叉树的遍历是指按照某种顺序依次访问二叉树中的每个节点。常见的遍历方式有先序遍历、中序遍历和后序遍历。先序遍历指先访问根节点,然后按照左子树、右子树的顺序依次遍历;中序遍历指先访问左子树,然后访问根节点,最后访问右子树;后序遍历指先访问左子树,然后访问右子树,最后访问根节点。
在已知二叉树的后序遍历和中序遍历的情况下,如何求出先序遍历呢?这里介绍一种基于递归的算法。
首先,我们知道后序遍历的最后一个节点一定是根节点。在中序遍历中,根节点左边的部分是左子树,右边的部分是右子树。因此,我们可以先根据后序遍历找到根节点,然后在中序遍历中找到根节点所在的位置,将中序遍历划分为左子树和右子树两部分。
接下来,我们可以递归地处理左子树和右子树。对于左子树,其后序遍历的最后一个节点是左子树的根节点,而中序遍历中根节点左边的部分是左子树。因此,我们可以递归地处理左子树,并将左子树的先序遍历拼接到根节点之后。对于右子树同理。
最后,我们将根节点的值加入先序遍历的结果中,即得到了完整的先序遍历。
下面是基于递归的代码实现:
```
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
index = inorder.index(root.val)
root.left = buildTree(inorder[:index], postorder[:index])
root.right = buildTree(inorder[index+1:], postorder[index:-1])
return root
def preorderTraversal(root):
if not root:
return []
return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root = buildTree(inorder, postorder)
preorder = preorderTraversal(root)
print(preorder)
```
运行结果为:[3, 9, 20, 15, 7]
这里通过buildTree函数先构建出二叉树,然后再通过preorderTraversal函数求出先序遍历。具体实现中,我们通过postorder[-1]找到根节点的值,再通过inorder.index(root.val)找到根节点在中序遍历中的位置,然后递归地处理左子树和右子树。最后,我们将根节点的值加入结果中,即得到了完整的先序遍历。
总之,根据后序遍历和中序遍历求先序遍历的方法可以通过递归实现。在实际应用中,这种方法可以用于解决一些二叉树遍历相关的问题。
您可能感兴趣的文章
相关推荐
热门阅读
-
圣城家园专区2022排行榜前十名下载-好玩的圣城家园专区大全
2024-09-05
-
郁闷什么意思
2024-09-05
-
cad怎么一次性打印所有图纸
2024-09-05
-
山东科大泰安校区怎么样
2024-09-05
-
轿车安装挡泥板好不好
2024-09-05
-
变角度空间桁架模型的基本假定是什么
2024-09-05
-
用自我介绍六字成语大全及解释图片
2024-09-05
-
z5次列车途经站点
2024-09-05
-
万圣节简易面具怎么做
2024-09-05
-
具有什么性质的化学品 属于化学危险品
2024-09-05
-
用自我介绍六字成语大全及解释图片
2024-09-05
-
z5次列车途经站点
2024-09-05
-
万圣节简易面具怎么做
2024-09-05
-
具有什么性质的化学品 属于化学危险品
2024-09-05
最新文章
-
五菱荣光发动机报故障灯
2024-09-05
-
路亚竿可以钓鲤鱼,草鱼吗视频
2024-09-05
-
形容孩子天真快乐,纯真的古诗词
2024-09-05
-
t244次列车经过的站点
2024-09-05
-
your和yours的区别和用法
2024-09-05
-
做纸杯蛋糕温度多少,烤多久
2024-09-05
-
家用什么样暖气片好一点
2024-09-05
-
六十天猜一个字谜
2024-09-05
-
花生四烯酸环氧酶代谢的产物
2024-09-05
-
6.8米货车运费多少钱一公里合适
2024-09-05
-
4月25日是什么星座女
2024-09-05
-
发动机功率的计算公式及单位换算
2024-09-05
-
水冷空调用电多少千瓦
2024-09-05
-
魔方怎么还原一面口诀图解
2024-09-05