算法刷题-二叉树

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路

广度优先搜索，答案就是二叉树的最右侧的节点
遍历每层的时候，就把len(queue)-1的节点加入到结果即可。

代码

# 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]:res=[]if not root:return resqueue=collections.deque([root])while queue:sz=len(queue)for i in range(sz):node =queue.popleft()if i == sz-1:res.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return res

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

思路

和上一题一样，本次到len(queue)-1的最后一个节点的时候，把计算的结果加入到结果中

代码

# 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]:res = []if not root:return resq = collections.deque([root])while q:sz = len(q)sum = 0for i in range(sz):t = q.popleft()sum += t.valif t.left:q.append(t.left)if t.right:q.append(t.right)if i == sz - 1:res.append(sum / sz)return  res

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的_层序遍历_。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

思路

广度优先搜索：每次不再区分左子树和右子树，直接遍历所有的children，加入队列

代码

class Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:res = []if not root:return resq = collections.deque([root])while q:sz = len(q)cur = []for i in range(sz):t = q.popleft()cur.append(t.val)for child in t.children:q.append(child)res.append(cur)return res

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

思路

广度优先搜索，每层开一个比$-2^{31}$还 小的数，然后不断更新这个为最大值

代码

class Solution:def largestValues(self, root: Optional[TreeNode]) -> List[int]:res = []if not root:return resq = collections.deque([root])while q:sz = len(q)mx = -10000000000for _ in range(sz):t = q.popleft()mx = max(mx, t.val)if t.left:q.append(t.left)if t.right:q.append(t.right)if _ == sz - 1:res.append(mx)return res