ssutsen / DS.

111-2師大科技系資料結構
0 stars 0 forks source link

199. Binary Tree Right Side View #11

Open ssutsen opened 1 year ago

ssutsen commented 1 year ago

Given the root of 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 1: image

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

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []
ssutsen commented 1 year ago

solution

# 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 = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result =[]
        queue = [root]
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                if i == size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result
ssutsen commented 1 year ago
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        q = deque([root])
        while q:
            if q[-1]:
                ans.append(q[-1].val)
            for i in range(len(q)):
                node = q.popleft()
                if node and node.left:
                    q.append(node.left)
                if node and node.right:
                    q.append(node.right)
        return ans

這是一個解決二叉樹右側視圖問題的 Python 3 代碼,使用了廣度優先搜索(BFS)算法。下面是代碼的解釋:

1.首先定義一個空列表 ans 來存儲右側視圖的節點值。

2.定義一個雙端隊列 q,並將二叉樹的根節點加入到隊列中。

3.在 while 循環中,如果隊列 q 不為空,則遍歷隊列中的每個節點。

4.如果隊列中的最後一個節點不為空,則將其值加入到 ans 列表中。

5.然後遍歷該層的所有節點,將其左右子節點加入到隊列中。

6.返回 ans 列表,即為二叉樹的右側視圖。

值得注意的是,在這個算法中,我們使用了雙端隊列而不是普通的隊列,這是為了方便在隊列的末尾取得最後一個節點,以便將其加入到 ans 列表中。