题目
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层序遍历结果：
[ [3], [9,20], [15,7] ]
解题
方法：迭代
广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。
广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def levelOrder(self, root): if not root: return [] res = [] queue = [root] while queue: # 获取当前队列的长度，这个长度相当于 当前这一层的节点个数 size = len(queue) tmp = [] # 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中 # 如果节点的左/右子树不为空，也放入队列中 for _ in range(size): r = queue.pop(0) tmp.append(r.val) if r.left: queue.append(r.left) if r.right: queue.append(r.right) # 将临时list加入最终返回结果中 res.append(tmp) return res
c++解法
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(!root) return {}; vector<vector<int>> res; queue<TreeNode*> queue; queue.push(root); while(!queue.empty()){ vector<int> tmp; int l=queue.size(); while(l--){ TreeNode* cur=queue.front(); queue.pop(); tmp.push_back(cur->val); TreeNode* left=cur->left; TreeNode* right=cur->right; if(left){ queue.push(left); } if(right){ queue.push(right); } } res.push_back(tmp); } return res; } };
java解法
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root==null) return new LinkedList<>(){}; List<List<Integer>> res=new LinkedList<>(); Queue<TreeNode> q=new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int l=q.size(); List<Integer> tmp=new LinkedList<>(); while((l--)>0){ TreeNode cur=q.poll(); tmp.add(cur.val); if(cur.left!=null){ q.add(cur.left); } if(cur.right!=null){ q.add(cur.right); } } res.add(tmp); } return res; } }
