๑◔◡◔๑
嗨，我是wec，今天是DAY 22。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個二叉樹，返回從右側看這棵樹所能看到的節點值的列表。

🔎 解題思路＆程式碼

1️⃣ 佇列

第1步： 使用廣度優先搜索(BFS)或深度優先搜索(DFS)來遍歷樹的節點，這邊我們選BFS。
第2步： 每當訪問到一層的最後一個節點時，將其加入結果列表。這樣可以確保只收集每層最右側的節點。
第3步： 返回結果列表，這就是從右側可見的節點值。
程式碼：

class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val=0, left=nil, right=nil)
    @val = val
    @left = left
    @right = right
  end
end

def right_side_view(root)
  return [] if root.nil?

  result = []
  queue = [root]

  while !queue.empty?
    level_size = queue.size

    (0...level_size).each do |i|
      node = queue.shift
      result << node.val if i == level_size - 1

      queue << node.left if node.left
      queue << node.right if node.right
    end
  end

  result
end

🔎 總結

時間複雜度

佇列： 時間複雜度為O(n)，n為組數長度。
➡️ 在BFS中，我們使用佇列來存儲當前層的節，。每次從佇列中取出一個節點時，這個節點的所有子節點都會被加入到佇列的尾部，在下一層遍歷。在每一層中，根據佇列的大小，我們可以得知當層有多少個節點，我們遍歷這些節點，並且記錄下每一層的最後一個節點，這樣就能得到從右側看到的節點了◝(⁰▿⁰)◜!!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃味覺糖。
明天要說：Ruby精選刷題！Medium路跑D-15(>∀･)⌒☆