#199. Binary Tree Right Side View

題目描述

給你一個二元樹的根節點root，想像你站在這棵樹的右邊，回傳你所能看到的由上至下排列的最右邊節點。

限制條件

節點數量介於[0, 100]之間。
-100 <= 節點值 <=100

解題思路

這一題直接使用寬度優先搜尋(Breadth First Search, BFS)就可以很好的解決。

BFS會以由上至下的順序一排一排的處理節點，所以可以很容易地辨識最靠右的節點是哪一個，因此可以順利的解決問題。

Brute Force

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var ans = new List<int>();
        if(root==null) return ans;        
        var q = new Queue();
        q.Enqueue(root);
        while(q.Count!=0){
            var len = q.Count;            
            for(int i=0;i<len;i++){
                var n = (TreeNode)q.Dequeue();
                if(i==len-1) ans.Add(n.val);
                if(n.left!=null) q.Enqueue(n.left);
                if(n.right!=null) q.Enqueue(n.right);
            }
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：由於會檢查所有的節點，因此時間複雜度為O(n)。
空間複雜度：Queue所佔用的空間最多為最底層的節點數量2ⁿ/2，因此空間複雜度為O(2ⁿ)。

學習重點

Breadth First Search(BFS)