Re: [閒聊] 每日LeetCode已回收
103. Binary Tree Zigzag Level Order Traversal
給一棵二元樹，
求他的 zigzag level order traversal，
也就是第一層從左到右，第二層從右到左，第三層從左到右，以此類推。
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation:
https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg
第一層從左到右得到 [3]
第二層從右到左得到 [20,9]
第三層從左到右得到 [15,7]
Example 2:
Input: root = [1]
Output: [[1]]
Explanation:
第一層從左到右得到[1]
Example 3:
Input: root = []
Output: []
Explanation:
沒有任何節點
解題思路:
一層一層從左到右做BFS，把該層節點的值存成陣列，
如果該層是偶數層就先把陣列反轉再存入答案之中。
C++ code:
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> que;
que.push(root);
bool left_to_right = true;
while(que.size() > 0){
vector<int> v;
int T = que.size();
while(T--){
TreeNode* node = que.front(); que.pop();
if(!node) continue;
que.push(node->left);
que.push(node->right);
v.push_back(node->val);
}
if(!left_to_right) reverse(v.begin(), v.end());
if(v.size()) ans.push_back(v);
left_to_right = !left_to_right;
}
return ans;
}
};
---
早上久違的嘗試線上賽，
我還以為直接點進去就能寫了，結果還在花時間填資料註冊，
而且發現有些設定跟 leetcode 不太一樣，像是範測不會自動判斷是不是 AC，
然後真的太久沒寫程式了都在 debug，
第三題也因為偷懶用 map 來做 DP 就 TLE 了，大改程式花了不少時間，
要是時間多一點應該四題都能寫完 QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676784514.A.740.html
※ 編輯: idiont (140.113.229.216 臺灣), 02/19/2023 13:38:58
推
02/19 14:14,
2年前
, 1F
02/19 14:14, 1F
討論串 (同標題文章)
完整討論串 (本文為第 239 之 719 篇)：