翻译资格考试

导航

根据后序和中序遍历求先序遍历

来源 :华课网校 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)找到根节点在中序遍历中的位置,然后递归地处理左子树和右子树。最后,我们将根节点的值加入结果中,即得到了完整的先序遍历。

总之,根据后序遍历和中序遍历求先序遍历的方法可以通过递归实现。在实际应用中,这种方法可以用于解决一些二叉树遍历相关的问题。

分享到

您可能感兴趣的文章

相关推荐

热门阅读

最新文章