Binary Tree Right Side View

题目描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

解题方法

一开始我以为只要不断地优先找右边的child就可以了，其实不对，因为如果只是不断地看右子树，会错过左子树depth大于右子树的情况，比如

   1            <---
 /   \
2     3         <---
 \     
  5             <---

所以这种简单的想法并不对，应该多画几个例子来看看有什么规律和没考虑到的地方

BFS level-order

我们可以很快想到之前做过的BFS level-order的方法，这里只要总是输出最右边的数就可以了。所以还是用BFS的方法做。

Solution

from collections import deque
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        queue = deque()
        result = []
        queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if i == size - 1:
                    result.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return result

Reference