首页 > 代码库 > [LeetCode] Binary Tree Zigzag Level Order Traversal（bfs）
[LeetCode] Binary Tree Zigzag Level Order Traversal（bfs）
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > res; if(root==NULL) return res; queue<TreeNode *> q; q.push(root); q.push(NULL); res = bfs(q); return res; }private: vector<vector<int> > bfs(queue<TreeNode *> q){ vector<vector<int> > res; vector<int> temp; bool needReverse = false; while(!q.empty()){ TreeNode *p = q.front(); q.pop(); if(p!=NULL){ temp.push_back(p->val); if(p->left!=NULL){ q.push(p->left); } if(p->right!=NULL){ q.push(p->right); } }else if(p==NULL ){ if(needReverse){ int len = temp.size(); for(int i=0,j=len-1;i<j;i++,j--) swap(temp[i],temp[j]); } res.push_back(temp); temp.clear(); needReverse = (!needReverse); if(!q.empty()) q.push(NULL); } }//end while return res; }//end bfs};
方法：用queue实现bfs，对树按层进行搜索，树的结点按层存入queue中，用NULL值标记本层的结束。用bool值按层取反决定本层的vector是否要逆置。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。