class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
from typing import List
class Solution:
# 迭代的想法
def levelOrderBottom1(self, root: TreeNode) -> List[List[int]]:

# 导入双向队列类
from collections import deque
# 如果链表为空,返回空列表
if not root:return []
# 定义一个双向队列
queue = deque()
# 在队列左边添加根节点
queue.appendleft(root)
# 定义一个空列表
last_list = []
# 进行循环
while queue:
# 定义一个当前列表,用来存放每一层节点的值
now_list = []
# 当前有几个节点就循环几次。
for _ in range(len(queue)):
# 弹出一个值,
value = queue.pop()
# 把弹出的值添加进入当前列表
now_list.append(value.val)
# 判断此节点有没有左右儿子,如果有的话,就将他们从队列左边加入
# 注意,想一下为什么hi从左边加入
if value.left:
queue.appendleft(value.left)
if value.right:
queue.appendleft(value.right)
# 这里也要讲当前列表插入最终列表的最左边。
last_list.insert(0,now_list)
return last_list
# 递归的想法
def levelOrderBottom2(self, root: TreeNode) -> List[List[int]]:
# 首先定义一个列表,用来存放最终的数据
res = []
# 定义递归函数,两个参数,一个是节点,一个是层数
def dfs(root,depth):
# 如果当前节点为空,函数无需向下进行
if not root:return
# 当函数走到链表每一层最左边的节点的时候,
# 就插入一个空列表,
if depth == len(res):
res.insert(0,[])
res[-(depth + 1)].append(root.val)
dfs(root.left,depth + 1)
dfs(root.right,depth + 1)
dfs(root,0)
return res
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/cong12586/p/13111039.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!