lc199+637. 二叉树的右视图（python）

lc199. 二叉树的右视图

---

每日几道leetcode刷刷题！
传送门

---

题目描述

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

示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

---

代码

# 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]:
        if not root:
            return []
        res = []
        quene = [root]
        while quene: 
            n = len(quene)
            for i in range(n):
                a = quene.pop(0)
                if i == n - 1: #注意，这里不能len(quene)-1,因为上面已经pop了
                    res.append(a.val)
                if a.left:
                    quene.append(a.left)
                if a.right:
                    quene.append(a.right)
        return res

---

总结

同样层次遍历（BFS），将单层的最后一个元素放进res中
关于BFS二叉树的层次遍历 传送门

类似题目 637. 二叉树的层平均值 题目描述

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

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

代码

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        res = []
        quene = [root]
        while quene:
            sum = 0
            n = len(quene) #该层的节点数
            for i in range(n):
                a = quene.pop(0)
                sum += a.val
                if a.left:
                    quene.append(a.left)
                if a.right:
                    quene.append(a.right)
            res.append(sum / n)
        return res