二叉树知道中序和后序怎么求前序代码

二叉树是计算机科学中的一个重要数据结构，其应用十分广泛。对于二叉树的几种遍历方式，其中前序、中序、后序是最重要的三种。一般来说，如果我们知道二叉树的中序遍历和后序遍历，我们可以很轻松地求出前序遍历。本文将从多个角度介绍二叉树知道中序和后序怎么求前序的代码。

一、基础知识

首先，我们需要了解二叉树的几种遍历方式。前序遍历，就是先遍历根节点，再遍历左子树，最后遍历右子树。中序遍历，就是先遍历左子树，再遍历根节点，最后遍历右子树。后序遍历，就是先遍历左子树，再遍历右子树，最后遍历根节点。

其次，我们需要知道如何通过两个遍历序列来重建二叉树。据一个叫做“构建二叉树算法”的原理，可以通过一棵二叉树的中序遍历和后序遍历来唯一确定一棵二叉树。这个算法的具体实现方式可以通过递归来完成。

二、递归实现

我们可以通过递归来实现二叉树的前序遍历。首先，我们需要在输入中序遍历和后序遍历的序列之后，对二叉树进行重建。具体实现如下:

```python

# Python 代码

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

def buildTree(inorder: List[int], postorder: List[int]) -> TreeNode:

if not inorder or not postorder:

return None

root = TreeNode(postorder[-1])

m = inorder.index(postorder[-1])

root.left = buildTree(inorder[:m], postorder[:m])

root.right = buildTree(inorder[m+1:], postorder[m:-1])

return root

```

接着，我们可以通过递归遍历树结构来输出前序遍历序列。具体实现如下：

```python

# Python 代码

def preorderTraversal(root: TreeNode) -> List[int]:

res = []

def dfs(node):

if not node:

return

res.append(node.val)

dfs(node.left)

dfs(node.right)

dfs(root)

return res

```

三、非递归实现

在实际操作中，非递归实现方式常常比递归方式更加高效，更加稳定。因此，我们可以通过栈和循环来实现二叉树的前序遍历。具体实现如下：

```python

# Python 代码

def preorderTraversal(root: TreeNode) -> List[int]:

if not root:

return []

res, stack = [], [root]

while stack:

node = stack.pop()

res.append(node.val)

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return res

```

四、时间复杂度和空间复杂度

通过对以上两个实现方式的分析，我们可以得出以下结论：递归实现和非递归实现方式所消耗的时间复杂度都是 O(n)，其中 n 为节点数。对于空间复杂度而言，递归实现方式所消耗的空间为 O(n)，而非递归实现方式所消耗的空间为 O(logn)。