音乐网站建设课的期末报告书,天猫网站企业网站专业性诊断分析,dk域名网站,做淘宝网站用什么软件有哪些难度#xff1a; 中等通过率#xff1a; 46.1%题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述
给定一个二叉树#xff0c;返回其按层次遍历的节点值。 #xff08;即逐层地#xff0c;从左到右访问所有节点…难度 中等通过率 46.1%题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述
给定一个二叉树返回其按层次遍历的节点值。 即逐层地从左到右访问所有节点。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回其层次遍历结果
[[3],[9,20],[15,7]
]基于队列的解法
维护一个队列从根节点开始遍历二叉树遇到一个节点后就将其放入队列下次遍历的节点从队列的头部取。这样得到的效果就是先入队的先被访问即先访问第一层而后第二层以此类推。最终就实现了层次遍历。
如果一次出队一个节点为了区别节点的层级需要加入层级信息。其实没有必要。可以一次性把同一层的节点全部出队并处理。
class Solution {
public:vectorvectorint levelOrder(TreeNode *root) {vectorvectorint res;queueTreeNode * queue_;if(root){queue_.push(root);}while(!queue_.empty()){int size queue_.size();vectorint nums;for (size_t i 0; i size; i){TreeNode* node queue_.front();queue_.pop();nums.push_back(node-val);if(node-left){queue_.push(node-left);}if(node-right){queue_.push(node-right);}}res.push_back(::move(nums));}return res;}
};递归解法
从根节点起采用先序遍历记录每个节点的层级把节点的值插入对应层级的数组中。
class Solution {
public:vectorvectorint levelOrder(TreeNode *root) {vectorvectorint res;traverse(root, 1, res);return res;}void traverse(TreeNode *root, size_t level, vectorvectorint res) {if (!root) {return;}if (res.size() level) {res.emplace_back();}res[level-1].push_back(root-val);traverse(root-left, level 1, res);traverse(root-right, level 1, res);}
};
