您好,登錄后才能下訂單哦!
今天小編給大家分享一下C++怎么實現(xiàn)二叉樹的字形層序遍歷的相關知識點,內容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
這道二叉樹的之字形層序遍歷是之前那道 Binary Tree Level Order Traversal 的變形,不同之處在于一行是從左到右遍歷,下一行是從右往左遍歷,交叉往返的之字形的層序遍歷。最簡單直接的方法就是利用層序遍歷,并使用一個變量 cnt 來統(tǒng)計當前的層數(shù)(從0開始),將所有的奇數(shù)層的結點值進行翻轉一下即可,參見代碼如下:
解法一:
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> res; queue<TreeNode*> q{{root}}; int cnt = 0; while (!q.empty()) { vector<int> oneLevel; for (int i = q.size(); i > 0; --i) { TreeNode *t = q.front(); q.pop(); oneLevel.push_back(t->val); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } if (cnt % 2 == 1) reverse(oneLevel.begin(), oneLevel.end()); res.push_back(oneLevel); ++cnt; } return res; } };
我們可以將上面的解法進行優(yōu)化一下,翻轉數(shù)組雖然可行,但是比較耗時,假如能夠直接計算出每個結點值在數(shù)組中的坐標,就可以直接進行更新了。由于每層的結點數(shù)是知道的,就是隊列的元素個數(shù),所以可以直接初始化數(shù)組的大小。此時使用一個變量 leftToRight 來標記順序,初始時是 true,當此變量為 true 的時候,每次加入數(shù)組的位置就是i本身,若變量為 false 了,則加入到 size-1-i 位置上,這樣就直接相當于翻轉了數(shù)組。每層遍歷完了之后,需要翻轉 leftToRight 變量,同時不要忘了將 oneLevel 加入結果 res,參見代碼如下:
解法二:
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> res; queue<TreeNode*> q{{root}}; bool leftToRight = true; while (!q.empty()) { int size = q.size(); vector<int> oneLevel(size); for (int i = 0; i < size; ++i) { TreeNode *t = q.front(); q.pop(); int idx = leftToRight ? i : (size - 1 - i); oneLevel[idx] = t->val; if (t->left) q.push(t->left); if (t->right) q.push(t->right); } leftToRight = !leftToRight; res.push_back(oneLevel); } return res; } };
我們也可以使用遞歸的方法來解,這里實際上用的是先序遍歷,遞歸函數(shù)需要一個變量 level 來記錄當前的深度,由于 level 是從0開始的,假如結果 res 的大小等于 level,就需要在結果 res 中新加一個空集,這樣可以保證 res[level] 不會越界。取出 res[level] 之后,判斷 levle 的奇偶,若其為偶數(shù),則將 node->val 加入 oneLevel 的末尾,若為奇數(shù),則加在 oneLevel 的開頭。然后分別對 node 的左右子結點調用遞歸函數(shù),此時要傳入 level+1 即可,參見代碼如下:
解法三:
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> res; helper(root, 0, res); return res; } void helper(TreeNode* node, int level, vector<vector<int>>& res) { if (!node) return; if (res.size() <= level) { res.push_back({}); } vector<int> &oneLevel = res[level]; if (level % 2 == 0) oneLevel.push_back(node->val); else oneLevel.insert(oneLevel.begin(), node->val); helper(node->left, level + 1, res); helper(node->right, level + 1, res); } };
以上就是“C++怎么實現(xiàn)二叉樹的字形層序遍歷”這篇文章的所有內容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關注億速云行業(yè)資訊頻道。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。