自下而上,从右到左的层次遍历算法
时间: 2023-06-17 17:05:08 浏览: 65
自下而上,从右到左的层次遍历算法可以用于遍历二叉树或者多叉树,其基本思想是先遍历最后一层节点,然后逐层向上遍历,直到根节点。
具体实现步骤如下:
1. 创建一个队列,将根节点入队;
2. 遍历队列中的每个节点,将其所有子节点(如果有)从右到左依次入队;
3. 将遍历得到的节点值保存到列表中;
4. 重复步骤2和步骤3,直到队列为空。
下面是Python实现代码:
```python
def levelOrderBottom(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue = [root]
res = []
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.insert(0, level)
return res
```
其中,res是一个列表,用于保存遍历结果。每次遍历一层节点后,将该层节点值插入到res的最前面,这样就可以实现自下而上、从右到左的遍历顺序。