【廣度優(yōu)先搜索】199.二叉樹的右視圖
給定一棵二叉樹，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點值。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
? ?1? ? ? ? ? ? <---
?/? ?\
2? ? ?3? ? ? ? ?<---
?\? ? ?\
? 5? ? ?4? ? ? ?<---
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
題目解析
找到?樹 右視圖，需要做的操作：
首先需要找到?每一層最右邊的值；
這些值的 集合 即為 答案
題目解答
方法：層次遍歷的 非遞歸方法
思路：
? 利用 層層次遍歷的?非遞歸方法?遍歷 每一層
保存每一層 的 最右邊一個元素；
最后這些值的 集合即為 答案
代碼展示
# 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 = rightclass Solution:def rightSideView(self, root: TreeNode) -> List[int]:'''方法：隊列迭代 (非遞歸)'''res = []if not root:return resqueue = collections.deque()queue.append(root)while queue:last = -999for i in range(len(queue)):node = queue.popleft()last = node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(last)return res
復(fù)雜度計算
?時間復(fù)雜度：O(N)，其中 N 是二叉樹的節(jié)點數(shù)。二叉樹的所有節(jié)點有且只會被訪問一次，因此時間復(fù)雜度為 O(N)。
-空間復(fù)雜度：O(N)，當(dāng)樹為平衡二叉樹時，最多有N/2個樹節(jié)點入隊，使用 O(N)?大小的額外空間
運行結(jié)果
評論
圖片
表情