层序遍历 10
102.二叉树的层序遍历 (opens new window)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
q_ = []
result = []
if root:
q_.append(root)
while q_:
size = len(q_)
sub_result = []
for i in range(size):
cur = q_.pop(0)
sub_result.append(cur.val)
if cur.left:
q_.append(cur.left)
if cur.right:
q_.append(cur.right)
result.append(sub_result)
return result
107.二叉树的层次遍历II
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
q_ = []
result = []
if root:
q_.append(root)
while q_:
level = []
size = len(q_)
for i in range(size):
cur = q_.pop(0)
level.append(cur.val)
if cur.left:
q_.append(cur.left)
if cur.right:
q_.append(cur.right)
result.insert(0, level)
return result
199.二叉树的右视图
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
q_ = []
lyr_tree = []
lyr = 0
if root:
q_.append(root)
while q_:
level = []
size = len(q_)
for i in range(size):
cur = q_.pop(0)
level.append(cur.val)
if cur.left:
q_.append(cur.left)
if cur.right:
q_.append(cur.right)
lyr_tree.append(level)
lyr += 1
result = []
for i in range(lyr):
result.append(lyr_tree[i][-1])
return result
637.二叉树的层平均值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q_ = []
result = []
if root:
q_.append(root)
while q_:
level = []
size = len(q_)
for i in range(size):
cur = q_.pop(0)
level.append(cur.val)
if cur.left:
q_.append(cur.left)
if cur.right:
q_.append(cur.right)
result.append(sum(level) / len(level))
return result
429.N叉树的层序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
q_ = []
result = []
if root:
q_.append(root)
while q_:
level = []
size = len(q_)
for i in range(size):
cur = q_.pop(0)
level.append(cur.val)
if cur.children:
for i in cur.children:
q_.append(i)
result.append(level)
return result
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
else:
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
111.二叉树的最小深度
226.翻转二叉树
101.对称二叉树 2