Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
|
1 2 3 4 5 |
3 / \ 9 20 / \ 15 7 |
return its level order traversal as:
|
1 2 3 4 5 |
[ [3], [9,20], [15,7] ] |
Solution 1: BFS O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(!root) return {}; vector<vector<int>> ans; vector<TreeNode*> curr,next; curr.push_back(root); while(!curr.empty()) { ans.push_back({}); for(TreeNode* node : curr) { ans.back().push_back(node->val); if(node->left) next.push_back(node->left); if(node->right) next.push_back(node->right); } curr.swap(next); next.clear(); } return ans; } }; |
Solution 2: DFS O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; DFS(root, 0 /* depth */, ans); return ans; } private: void DFS(TreeNode* root, int depth, vector<vector<int>>& ans) { if(!root) return; // Works with pre/in/post order while(ans.size()<=depth) ans.push_back({}); ans[depth].push_back(root->val); // pre-order DFS(root->left, depth+1, ans); DFS(root->right, depth+1, ans); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment