首页 > 代码库 > leetcode 题解:Binary Tree Level Order Traversal (二叉树的层序遍历)
leetcode 题解:Binary Tree Level Order Traversal (二叉树的层序遍历)
题目：
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,#,#,15,7},
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
说明：
1）层序遍历，每层单独输出，顺序：从上到下，从左到右（思考：从下到上，从右到左如何？下面会说明）
2）实现也分递归和迭代，其中迭代贴出了两种实现（思想基本相同）
实现：
一、递归实现
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 vector<vector<int> > levelOrder(TreeNode *root) {13 vector<vector<int>> result;14 traverse(root,1,result);15 return result;16 }17 void traverse(TreeNode *root,size_t level,vector<vector<int>> &result)18 {19 if(root==nullptr) return;20 if(level>result.size()) result.push_back(vector<int>());21 result[level-1].push_back(root->val);22 traverse(root->left,level+1,result);23 traverse(root->right,level+1,result);24 }25 };
二、迭代实现
a 迭代实现1
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 /*常规层序遍历思想，每层入队结束压入一个空节点，作为标志*/11 class Solution {12 public:13 vector<vector<int> > levelOrder(TreeNode *root) {14 vector<vector<int>> vec_vec_tree;//创建空vector,存放最后返回的遍历二叉树的值15 vector<int> level;//创建空的vector，存放每一层的遍历二叉树的值16 TreeNode *p=root;17 if(p==nullptr) return vec_vec_tree;//如果二叉树空，返回空vector<vector<int>> 18 queue<TreeNode *> queue_tree;//创建一个空队列19 queue_tree.push(p);//root节点入队列20 queue_tree.push(nullptr);//空节点入队列21 while(!queue_tree.empty())//直到队列为空22 {23 p=queue_tree.front(); //头结点取值，并出队列24 queue_tree.pop();25 if(p==nullptr&&!level.empty())//节点为空并且队列不为空26 {27 queue_tree.push(nullptr);//入队空节点，与下一层隔开28 vec_vec_tree.push_back(level);//已遍历的层入队29 level.clear();//清空vecor level30 }31 else if(p!=nullptr)//如果节点不空32 {33 level.push_back(p->val);//遍历34 if(p->left) queue_tree.push(p->left);//若有左右孩子，则入队列35 if(p->right) queue_tree.push(p->right);//注意入队顺序：先左后右36 }37 38 }39 return vec_vec_tree;40 }41 };
b 迭代实现2
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 /*两个队列实现*/11 class Solution {12 public:13 vector<vector<int> > levelOrder(TreeNode *root) {14 vector<vector<int> > result;15 if(root == nullptr) return result;16 queue<TreeNode*> current, next;//两个队列，保存当层（current）和下层（next）节点17 vector<int> level; // 存放每层的节点值18 current.push(root);19 while (!current.empty())//直到二叉树遍历完成20 {21 while (!current.empty())//直到本层二叉树遍历完成22 {23 TreeNode* node = current.front();//取队首节点，出队列24 current.pop();25 level.push_back(node->val);//访问节点值26 if (node->left != nullptr) next.push(node->left);//若存在左右节点，则压入next队列中27 if (node->right != nullptr) next.push(node->right);//注意入队顺序为先left后right28 }29 result.push_back(level);//压入总vector30 level.clear();//清vector31 swap(next, current);//next队列和current队列交换32 }33 return result;34 }35 };
最后说明：如果 从下到上，从右到左如何遍历，如何实现
我的想法：从下到上，直接把结果vector<vector<int>>逆序即可
从右到左，把入队顺序改为先右后左即可
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。