0199._binary_tree_right_side_view.md

199. Binary Tree Right Side View

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/binary-tree-right-side-view/description/

内容描述

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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

还是在玩第102题，level order traversal. beats 100%

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
      
        res = []
        cur_level = [root]
        while cur_level:
            next_level, tmp_res = [], []
            for node in cur_level:
                tmp_res.append(node.val)
                if node.left: 
                    next_level.append(node.left)
                if node.right: 
                    next_level.append(node.right)
            res.append(tmp_res[-1])
            cur_level = next_level
        return res