199. 二叉树的右视图

Difficulty

Medium

法1：宽度优先搜索

思路

同

🥎

102. 二叉树的层序遍历及

🛷

107. 二叉树的层序遍历 II 类似。只不过是只保存了每层最后一个节点

解答


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue) # 记录每一层有几个节点
            temp_val = None
            while temp_len > 0:
                temp_node = queue.pop(0)
                if temp_len == 1:  # 只保存最后的值
                    temp_val = temp_node.val 
								# 将该节点的子节点放到队列中
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
                temp_len -= 1
            result.append(temp_val) # 将该层的最后一个值保存到result
        return result

法2 深度优先搜索

思路

同

🥎

102. 二叉树的层序遍历深度优先搜索类似，采用 前右左 的顺序遍历，利用depth变量来辅助计算当前层数，如果当前层 == result中结果的个数，那么说明当前层还没有节点被加进去，由于是前右中的遍历，所以将当前节点加进去就一定是最右边的节点，之后，len(result) 就会大于depth，所以当前层的其余左边的节点就不会被加进去了。

💡

1. 因为一层肯定要添加一个节点，添加过之后 depth < len(result）所以其他节点就不会进去了。 2. 又因为是前右左顺序遍历，所以第一次加进去的节点一定是最右边的节点。

题解


# 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: TreeNode) -> List[int]:
        res = []
        self.dfs(node=root, depth=0, result=res)
        return res

    def dfs(self, node, depth, result):
        if node is None:
            return None
        # 一层只添加一个数字，那么采用前右左的顺序，
        # 先将当前节点添加进去后，len(result)就会大于depth,那么该层其余的节点就不会被加进去了
        if depth == len(result):
            result.append(node.val)
        self.dfs(node.right, depth+1, result)
        self.dfs(node.left, depth+1, result)