根据后序和中序遍历求先序遍历
来源 :华课网校 2024-09-02 23:11:39
中二叉树的遍历是指按照某种顺序依次访问二叉树中的每个节点。常见的遍历方式有先序遍历、中序遍历和后序遍历。先序遍历指先访问根节点,然后按照左子树、右子树的顺序依次遍历;中序遍历指先访问左子树,然后访问根节点,最后访问右子树;后序遍历指先访问左子树,然后访问右子树,最后访问根节点。
在已知二叉树的后序遍历和中序遍历的情况下,如何求出先序遍历呢?这里介绍一种基于递归的算法。
首先,我们知道后序遍历的最后一个节点一定是根节点。在中序遍历中,根节点左边的部分是左子树,右边的部分是右子树。因此,我们可以先根据后序遍历找到根节点,然后在中序遍历中找到根节点所在的位置,将中序遍历划分为左子树和右子树两部分。
接下来,我们可以递归地处理左子树和右子树。对于左子树,其后序遍历的最后一个节点是左子树的根节点,而中序遍历中根节点左边的部分是左子树。因此,我们可以递归地处理左子树,并将左子树的先序遍历拼接到根节点之后。对于右子树同理。
最后,我们将根节点的值加入先序遍历的结果中,即得到了完整的先序遍历。
下面是基于递归的代码实现:
```
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)找到根节点在中序遍历中的位置,然后递归地处理左子树和右子树。最后,我们将根节点的值加入结果中,即得到了完整的先序遍历。
总之,根据后序遍历和中序遍历求先序遍历的方法可以通过递归实现。在实际应用中,这种方法可以用于解决一些二叉树遍历相关的问题。
您可能感兴趣的文章
相关推荐
热门阅读
-
sled如何读
2024-09-02
-
琴叶榕的养护和注意事项
2024-09-02
-
好听的qq分组名称古风霸气
2024-09-02
-
动态桌面怎么设置 视频
2024-09-02
-
车遥控器电池怎么更换的
2024-09-02
-
正常车轮胎可以用几年
2024-09-02
-
兔眼蓝莓花期一般在( )月份?
2024-09-02
-
择天记魔族黑袍露面
2024-09-02
-
胡桃里创始人李华宾哪里人
2024-09-02
-
综合用地50年产权到期后怎么办
2024-09-02
-
兔眼蓝莓花期一般在( )月份?
2024-09-02
-
择天记魔族黑袍露面
2024-09-02
-
胡桃里创始人李华宾哪里人
2024-09-02
-
综合用地50年产权到期后怎么办
2024-09-02
最新文章
-
俏江南对赌协议是什么时候
2024-09-02
-
怎么用对讲机打电话教学视频
2024-09-02
-
送给喝酒人的一句话
2024-09-02
-
为什么qq头像更换不了怎么办
2024-09-02
-
车船税的照片长什么样子
2024-09-02
-
明代初学者黄宗羲认为西方的几何学来源于
2024-09-02
-
液力偶合器是什么材料做的好
2024-09-02
-
牡丹花的诗句千古名句
2024-09-02
-
青梅酒用什么泡的
2024-09-02
-
我的世界中怎么用红石做一个自动门
2024-09-02
-
如何做v型回旋镖手工教程
2024-09-02
-
鸟巢的占地面积是多少北京
2024-09-02
-
男生用洗面奶有什么好处
2024-09-02
-
12年福特福克斯怎么样?
2024-09-02