題目描述

給定一棵二叉樹，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值。

示例

輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:

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

解答方法

方法一：廣度優(yōu)先搜索

思路

從上至下一層一層遍歷二叉樹，每層從左至右遍歷當(dāng)前層所有節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)儲存起來作為下一層要遍歷的節(jié)點(diǎn)，將當(dāng)前層的最后一個(gè)節(jié)點(diǎn)的值添加至最終結(jié)果，直到所有層遍歷完畢

代碼

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        temp_layer = [root]
        while temp_layer:
            next_layer=[]
            for i in temp_layer:
                if i.left:
                    next_layer.append(i.left)
                if i.right:
                    next_layer.append(i.right)
            result.append(temp_layer[-1].val)
            temp_layer = next_layer
        return result

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

空間復(fù)雜度 : O(n)。由于廣度優(yōu)先搜索逐層訪問整棵樹，在訪問最大的層之前，隊(duì)列將最大。該層最壞的情況下可能有 0.5n=O(n) 大?。ㄒ豢猛暾亩鏄洌?/p>