给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
时间: 2024-01-21 16:42:56 浏览: 162
算法之二叉树的层序遍历(利用队列实现,需熟练手写)
5星 · 资源好评率100%
我们可以借助队列实现二叉树的层序遍历。具体步骤如下:
1. 根据后序遍历和中序遍历构建二叉树。
2. 初始化一个队列,将根结点入队。
3. 计算队列中的结点个数,依次出队并将其左右子结点入队。
4. 将出队的结点值存入结果列表中。
5. 重复步骤3-4,直到队列为空。
下面是实现的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder, postorder):
if not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = buildTree(inorder[:idx], postorder[:idx])
root.right = buildTree(inorder[idx+1:], postorder[idx:-1])
return root
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level_size = len(queue)
level_nodes = []
for i in range(level_size):
node = queue.pop(0)
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_nodes)
return res
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root = buildTree(inorder, postorder)
print(levelOrder(root)) # Output: [[3], [9, 20], [15, 7]]
```
时间复杂度:$O(n^2)$。每个节点入队出队各一次,总共需要$n$次操作,每次操作需要计算队列中的结点个数,最坏情况下需要遍历整棵树,因此总时间复杂度为$O(n^2)$。
空间复杂度:$O(n)$。队列中最多同时存储一层的结点,因此空间复杂度为$O(n)$。
阅读全文