[Leetcode]102.二叉树的层次遍历

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] 思路

层次遍历实际上就是使用广度优先遍历(BFS)从root开始遍历。我们学数据结构的时候知道,BFS一般用队列作辅助,DFS一般用栈进行辅助。
所以在这一题我们使用队列辅助进行广度优先遍历。每次pop一个元素,就判断其有无左右孩子,若有则将孩子加进队列。

这一题的一个难点是,如何区分层次,使不同层次的数在不同的行上?
遇到这种情况我们一般用一个标记值,而这题的队列存储的是地址。所以我们将NULL设为这个标记值。
作用是:每当一个层次的数全部pop()后,紧随其后的就是NULL。也就是在队列中用NULL把各个层次分开。
我们首先初始的时候在root后加一个NULL。之后的过程中每读到一个NULL就push一个新的NULL。

class Solution { public: vector<vector<int>> levelOrder(TreeNode *root) { if (root == NULL) return {}; vector<vector<int>> ans; queue<TreeNode *> temp; temp.push(root); temp.push(NULL); vector<int> cur_vec; while(!temp.empty()){ TreeNode *t = temp.front(); temp.pop(); if(t==NULL){ ans.push_back(cur_vec); cur_vec.resize(0); if(temp.size()>0){ temp.push(NULL); } }else{ cur_vec.push_back(t->val); if(t->left) temp.push(t->left); if(t->right) temp.push(t->right); } } return ans; } };

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpypwg.html