二叉树 从前序遍历得到二叉树
时间: 2023-11-14 16:06:16 浏览: 36
从前序遍历序列中还原二叉树的过程可以通过递归来实现。具体的步骤如下:
1. 创建一个全局变量,用于记录当前遍历到的节点在前序遍历序列中的索引,初始值为0。
2. 创建一个递归函数,函数参数包括前序遍历序列和当前子树的边界索引(start和end)。
3. 在递归函数中,首先判断边界索引是否合法(start大于end),如果不合法,则返回null。
4. 创建一个新节点,将前序遍历序列中当前索引位置的值赋给新节点。
5. 将全局索引值加1。
6. 在递归函数中,将当前子树的边界索引分为左子树和右子树的边界,并分别递归调用递归函数,传入左子树和右子树的边界索引。
7. 将递归调用返回的左子树和右子树连接到新节点上。
8. 返回新节点作为当前子树的根节点。
以下是使用Python示例代码实现从前序遍历得到二叉树的过程:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, start, end):
# 边界索引不合法,返回null
if start > end:
return None
# 创建当前子树的根节点
root = TreeNode(preorder[buildTree.index])
buildTree.index += 1
# 划分左子树和右子树的边界索引,并递归调用
root.left = buildTree(preorder, start, buildTree.index-1)
root.right = buildTree(preorder, buildTree.index, end)
return root
def buildTreeFromPreorder(preorder):
buildTree.index = 0 # 初始化全局索引为0
return buildTree(preorder, 0, len(preorder)-1)
# 示例调用
preorder = [3, 9, 20, 15, 7]
root = buildTreeFromPreorder(preorder)
```
以上代码中,通过定义一个全局索引变量 `buildTree.index` 来记录当前遍历到的节点位置,初始值为0。然后通过递归调用 `buildTree()` 函数来构建二叉树。最后返回根节点即可。