本文共 2009 字,大约阅读时间需要 6 分钟。
典型的BFS算法!
思路一开始没想到,按照书上的思路写的答案。。。 注意:deque是双向队列,在头尾插入都很快!/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: vector PrintFromTopToBottom(TreeNode* root) { vector res; if(root == NULL) return res; dequedeque; deque.push_back(root); while(!deque.empty()){ int a = deque.front()->val; res.push_back(a); if(deque.front()->left != NULL) deque.push_back(deque.front()->left); if(deque.front()->right != NULL) deque.push_back(deque.front()->right); deque.pop_front(); } return res; }};
deque que; //定义了一个整型的双端队列;que.front(); //返回容器que的第一个元素的引用。如果que为空,则该操作为空。que.pop_back(); //删除最后一个数据。que.pop_front(); //删除头部数据。que.push_back(elem); //在尾部加入一个数据。que.push_front(elem); //在头部插入一个数据。
2018年9月1日重做,利用队列做就行queue
/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x): val(x), left(NULL), right(NULL) { }};*/class Solution {public: vector PrintFromTopToBottom(TreeNode* root) { vector res; if (root == NULL) return res; queuetree_queue; tree_queue.push(root); while (!tree_queue.empty()) { int temp = tree_queue.front()->val; res.push_back(temp); if (tree_queue.front()->left) tree_queue.push(tree_queue.front()->left); if (tree_queue.front()->right) tree_queue.push(tree_queue.front()->right); tree_queue.pop(); } return res; }};
queue que; //定义了一个整型的双端队列que.front(); //返回容器que的头部元素que.pop(); //删除头部数据que.push(elem) //在尾部加入一个数据/*和栈stack的成员函数差不多*/
转载地址:http://bxhdb.baihongyu.com/