[LeetCode]199 二叉树的右视图

题目描述

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

示例

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

思路

  • 层序遍历
  • 先遍历右子树, 后遍历左子树
  • 第一次遇到下一层的就记录下来

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution:
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:return []
        ret = [root.val]
        q = deque()
        q.append((root,0))
        lv = 0
        while q:
            nd,cur = q.popleft()
            if cur==lv+1:
                ret.append(nd.val)
                lv+=1
            if nd.right:q.append((nd.right,lv+1))
            if nd.left:q.append((nd.left,lv+1))
        return ret