给出构造先序序列和层序序列对应的所有二叉树的实现
时间: 2024-05-10 22:21:32 浏览: 5
我们可以通过递归的方式来实现给定先序序列和层序序列构造二叉树的过程。
具体实现步骤如下:
1.定义二叉树结构体
首先,我们需要定义二叉树结构体,包括节点值和左右子节点的指针。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
2.递归构造二叉树
接着,我们可以定义一个递归函数来构造二叉树。该函数的输入参数包括先序序列和层序序列,以及根节点在先序序列中的位置、子树在层序序列中的起始位置和结束位置。
```python
def buildTree(preorder, inorder):
if not preorder:
return None
# 根节点为先序序列的第一个节点
root_val = preorder[0]
root = TreeNode(root_val)
# 划分左右子树
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = []
right_preorder = []
# 根据左右子树在中序序列中的位置,划分先序序列
for val in preorder[1:]:
if val in left_inorder:
left_preorder.append(val)
else:
right_preorder.append(val)
# 递归构造左右子树
left_start = 0
left_end = len(left_inorder) - 1
right_start = len(left_inorder)
right_end = len(inorder) - 2
root.left = buildTree(left_preorder, left_inorder, left_start, left_end, levelorder)
root.right = buildTree(right_preorder, right_inorder, right_start, right_end, levelorder)
return root
```
在递归函数中,我们首先根据先序序列的第一个节点来构造根节点。然后,根据根节点在中序序列中的位置,将中序序列划分为左右子树,并将先序序列也划分为左右子树。接着,我们递归构造左右子树,并将其连接到根节点上。
3.获取层序序列
最后,我们需要实现一个函数来获取给定二叉树的层序序列。该函数可以使用队列来实现广度优先遍历,将每层节点的值添加到结果列表中。
```python
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
size = len(queue)
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
完整代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder:
return None
# 根节点为先序序列的第一个节点
root_val = preorder[0]
root = TreeNode(root_val)
# 划分左右子树
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = []
right_preorder = []
# 根据左右子树在中序序列中的位置,划分先序序列
for val in preorder[1:]:
if val in left_inorder:
left_preorder.append(val)
else:
right_preorder.append(val)
# 递归构造左右子树
left_start = 0
left_end = len(left_inorder) - 1
right_start = len(left_inorder)
right_end = len(inorder) - 2
root.left = buildTree(left_preorder, left_inorder, left_start, left_end, levelorder)
root.right = buildTree(right_preorder, right_inorder, right_start, right_end, levelorder)
return root
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
size = len(queue)
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
参考链接:
- [LeetCode 题解](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/gong-shui-san-xie-yi-ti-shuang-jie-ti-rua-39f5/)
- [算法基础课](https://www.acwing.com/video/2574/)