用栈实现二叉树层次遍历算法
时间: 2023-10-02 15:07:57 浏览: 48
二叉树的层次遍历需要用到队列,而不是栈。在队列中存储每个节点,依次将每个节点的左右子节点入队,直到队列为空。
以下是用队列实现层次遍历的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode):
if not root:
return []
queue = [root]
result = []
while queue:
level_length = len(queue)
level = []
for i in range(level_length):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
```
如果一定要使用栈实现,可以考虑使用两个栈,一个存储当前层的节点,一个存储下一层的节点,每次遍历完当前层后将下一层节点栈中的元素倒序压入当前层节点栈中。不过这种实现方式比较复杂,效率不如队列实现。