根据后序和中序遍历求先序遍历
来源 :华课网校 2024-07-31 07:48:23
中二叉树的遍历是指按照某种顺序依次访问二叉树中的每个节点。常见的遍历方式有先序遍历、中序遍历和后序遍历。先序遍历指先访问根节点,然后按照左子树、右子树的顺序依次遍历;中序遍历指先访问左子树,然后访问根节点,最后访问右子树;后序遍历指先访问左子树,然后访问右子树,最后访问根节点。
在已知二叉树的后序遍历和中序遍历的情况下,如何求出先序遍历呢?这里介绍一种基于递归的算法。
首先,我们知道后序遍历的最后一个节点一定是根节点。在中序遍历中,根节点左边的部分是左子树,右边的部分是右子树。因此,我们可以先根据后序遍历找到根节点,然后在中序遍历中找到根节点所在的位置,将中序遍历划分为左子树和右子树两部分。
接下来,我们可以递归地处理左子树和右子树。对于左子树,其后序遍历的最后一个节点是左子树的根节点,而中序遍历中根节点左边的部分是左子树。因此,我们可以递归地处理左子树,并将左子树的先序遍历拼接到根节点之后。对于右子树同理。
最后,我们将根节点的值加入先序遍历的结果中,即得到了完整的先序遍历。
下面是基于递归的代码实现:
```
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)找到根节点在中序遍历中的位置,然后递归地处理左子树和右子树。最后,我们将根节点的值加入结果中,即得到了完整的先序遍历。
总之,根据后序遍历和中序遍历求先序遍历的方法可以通过递归实现。在实际应用中,这种方法可以用于解决一些二叉树遍历相关的问题。
您可能感兴趣的文章
相关推荐
热门阅读
-
闪烁之光汉化破解版
2024-07-31
-
手机怎么看国庆阅兵直播节目
2024-07-31
-
惠州优信达二手车2023
2024-07-31
-
禁止左转会被摄像头拍到吗?
2024-07-31
-
电瓶加水加什么水最好
2024-07-31
-
红绿灯左转车道直行算闯红灯吗了怎么办
2024-07-31
-
aj6口袋真假对比
2024-07-31
-
胆机功放的使用寿命多久?
2024-07-31
-
win11你的电脑未正确启动
2024-07-31
-
仔仔细细是成语吗
2024-07-31
-
aj6口袋真假对比
2024-07-31
-
胆机功放的使用寿命多久?
2024-07-31
-
win11你的电脑未正确启动
2024-07-31
-
仔仔细细是成语吗
2024-07-31
最新文章
-
中国的卡通人物有很多英语
2024-07-31
-
微信群聊名称大全朋友圈怎么改
2024-07-31
-
材料题作文素材大全
2024-07-31
-
天空中的启明星是什么星座
2024-07-31
-
女人梦到白蛇预示着什么预兆
2024-07-31
-
感动的近义词是什么呀英语
2024-07-31
-
cad小键盘怎么关闭
2024-07-31
-
日本久光镇痛贴效果怎么样
2024-07-31
-
广电网络手机连不上,可以看电视
2024-07-31
-
鸡肉怎么做吃起来比较嫩
2024-07-31
-
永康是金华的县级市么?
2024-07-31
-
路由器p/n是什么意思
2024-07-31
-
曹操战宛城歇后语下一句
2024-07-31
-
迪士尼密码箱的密码忘记了怎么打开手机
2024-07-31