l2-011 玩转二叉树python
时间: 2023-10-12 14:55:58 浏览: 104
l2-011 是杭电OJ上的一道题目,题目要求是给定一个二叉树的前序遍历和中序遍历结果,要求输出该二叉树的层次遍历结果。
下面是一个用 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, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
def levelOrder(root):
if not root:
return []
result = []
queue = [root]
while queue:
level_vals = []
level_size = len(queue)
for _ in range(level_size):
node = queue.pop(0)
level_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_vals)
return result
# 测试
preorder = [1, 2, 4, 8, 9, 5, 3, 6, 7]
inorder = [8, 4, 9, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
result = levelOrder(root)
print(result)
```
这段代码首先定义了一个 `TreeNode` 类,用于表示二叉树的节点。然后通过 `buildTree` 函数根据前序遍历和中序遍历结果构建出二叉树。最后使用 `levelOrder` 函数对构建好的二叉树进行层次遍历,并输出结果。
希望对你有帮助!如果有其他问题,请随时提问。