class Solution { public: vectorlevelOrder(TreeNode* root) { if(root==nullptr)return {};//判空 queue que;//层次遍历属于广度优先搜索,用队列来存储 que.push(root);//将根结点放入队列 vector vec; while(!que.empty()){//当队列不为空,d出队首元素,并且,将该元素插入数组 TreeNode *res=que.front();//res节点指向队列第一个元素 que.pop(); vec.push_back(res->val); if(res->left){//如果当前节点有左孩子,左孩子入队 que.push(res->left); } if(res->right){//如果当前节点有右孩子,右孩子入队 que.push(res->right); } } return vec; } };
剑指offer32-II、从上到下打印二叉树
class Solution { public: vector> levelOrder(TreeNode* root) { if(root==nullptr)return {}; vector >vec; queue que; TreeNode *last=root;//标记二叉树当前行的最后一个节点 TreeNode *nlast=nullptr;//下一行的最后一个节点 que.push(root); int i=0; vec.push_back({});//二维数组新增一行 while(!que.empty()){ TreeNode *res=que.front(); que.pop(); vec[i].push_back(res->val); if(res->left){ que.push(res->left); nlast=res->left; } if(res->right){ que.push(res->right); nlast=res->right; } if(res==last){ last=nlast;// vec.push_back({});//每到二叉树最后一个元素之后就给二维数组添加一行 i++;//用i做标记,数组元素要添加到vec[i]行 } } vec.pop_back();//删除二维数组中最后多加的一行一维数组 return vec; } };
剑指offer32-III、从上到下打印二叉树
class Solution { public: vector> levelOrder(TreeNode* root) { if(root==nullptr)return {}; vector >vec; queue que; TreeNode *last=root;//标记二叉树当前行的最后一个节点 TreeNode *nlast=nullptr;//下一行的最后一个节点 que.push(root); int i=0; vec.push_back({});//二维数组新增一行 while(!que.empty()){ TreeNode *res=que.front(); que.pop(); vec[i].push_back(res->val); if(res->left){ que.push(res->left); nlast=res->left; } if(res->right){ que.push(res->right); nlast=res->right; } if(res==last){ if(i%2!=0){//i为奇数时当前行需要被翻转 reverse(vec[i].begin(),vec[i].end()); } last=nlast; vec.push_back({});//每到二叉树最后一个元素之后就给二维数组添加一行 i++;//用i做标记,数组元素要添加到vec[i]行 } } vec.pop_back();//删除二维数组中最后多加的一行一维数组 return vec; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)