首页 > 代码库 > 102. Binary Tree Level Order Traversal (Tree, Queue; BFS)
102. Binary Tree Level Order Traversal (Tree, Queue; BFS)
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],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
思路:层次遍历用队列来实现,这里因为需要知道在哪一层,所以需要用两个队列/或者创建一个数据结构,包含TreeNode以及level信息。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<queue<TreeNode*>> q(2); int curIndex = 0; int nextIndex = 1; vector<int> retItem; vector<vector<int>> ret; if(root) q[curIndex].push(root); while(!q[curIndex].empty()){ retItem.push_back(q[curIndex].front()->val); if(q[curIndex].front()->left) q[nextIndex].push(q[curIndex].front()->left); if(q[curIndex].front()->right) q[nextIndex].push(q[curIndex].front()->right); q[curIndex].pop(); if(q[curIndex].empty()){ //end of this level ret.push_back(retItem); retItem.clear(); curIndex = (curIndex+1) & 0x01; nextIndex = (nextIndex+1) & 0x01; } } return ret; } };
102. Binary Tree Level Order Traversal (Tree, Queue; BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。