【LeetCode】#199. Binary Tree Right Side View詳細完整解法

Binary Tree Right Side View

題目描述

給你一個二元樹，想像你站在樹的右邊，回傳所有你能看到的整棵樹由上到下的右邊節點值。

其他限制條件

• 節點數量為［0, 100］。
• 節點值為［-100, 100］。

解題思路

從題目給出的範例來看，似乎是只要給出右邊的節點就好了。

Input：
      1
    /   \
   2     3
    \     \
     5     4
Output：
   [1 ,3 ,4]

但是不要忘了其中一段描述，是從上到下所有看的到的右邊節點。

從上面範例給出的樹可以知道，樹不一定是平衡的，所以可能會產生以下的狀況。

Input：
      1
    /   \
   2     3
    \     \
     5     4
    /
   9
Output：
   [1 ,3 ,4 ,9]

因此不能使用DFS一次找完所有右邊的節點。

這邊我們需要找到的是每一層的最右邊的節點，所以BFS是比較適合的選擇。

程式碼：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {}; //空節點保護
        vector<int> ans;
        queue<TreeNode*> q;
        q.push(root);

	    //使用queue進行BFS探索
        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
		        //把每一個節點的最右邊放入答案內
                if(i==n-1) ans.push_back(q.front()->val);
                if(q.front()->left) q.push(q.front()->left);
                if(q.front()->right) q.push(q.front()->right);
                q.pop();
            }                
        }
        return ans;
    }
};

時間複雜度分析

因為要跑完每一層的節點，所以時間複雜度為O（n）。

空間複雜度分析

最好的狀況下每一層的節點都以倍數增長，最後會接近O（1），最壞的狀況下只會有一條直線的節點，節點數量跟答案剛好會相等，所以會是O（n）。