来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目描述
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示:
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间
解题思路
利用一个队列记录当前层的结点,一个队列记录下一层的结点,遍历当前层就将下一层作为当前层进行遍历。注意判断结点为空的条件
代码展示
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> vviRet; queue<Node*> visiting; if(!root) return vviRet; visiting.push(root); while(!visiting.empty()) { queue<Node*> ch = visiting; visiting = queue<Node*>(); vector<int> viRet; while(!ch.empty()) { auto p = ch.front(); ch.pop(); viRet.push_back(p->val); for(auto iter: p->children) if(iter) visiting.push(iter); } vviRet.push_back(viRet); } return vviRet; } };
运行结果