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】 刷題地圖 - 人生自習室