【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)。

在〈【LeetCode】#199. Binary Tree Right Side View詳細完整解法〉中有 1 則留言

  1. 自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

回到頂端