https://leetcode.com/problems/n-ary-tree-level-order-traversal/

日期	是否一次通过	comment
2018-12-12 21:56	非递归1次通过，递归看答案	没掌握bfs，用数字表示层级
2018-12-15 23:36	一次通过	有感觉 or 状态好？
2018-01-16 23:36	一次通过	本质是先序遍历

image.png

（来源：https://leetcode.com/problems/n-ary-tree-level-order-traversal/）

null不存进queue/ stack是个好习惯

---

递归

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        helper(root, 0, result);
        return result;
    }
    
    private void helper(Node root, int level, List<List<Integer>> result) {
        if(root == null) {
            return;
        }
        
        List<Integer> oneLevel;
        if(level >= result.size()) {
             result.add(new ArrayList<>());
        } 

        result.get(level).add(root.val);
        for(Node node : root.children) {
            if(node == null) {
                continue;
            }
            helper(node, level+1, result);
        }
    }
}

非递归

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        
        Queue<Node> nodeQ = new LinkedList<>();
        nodeQ.offer(root);
        while(!nodeQ.isEmpty()) {
            int qLen = nodeQ.size();
            List<Integer> tempList = new ArrayList<>();
            for(int i=0; i<qLen; i++) {
                Node tempNode = nodeQ.poll();
                tempList.add(tempNode.val);
                for(Node nodeCd : tempNode.children) {
                    if(nodeCd == null) {     // null不存进queue/ stack是个好习惯 
                        continue;
                    }
                    nodeQ.offer(nodeCd);
                }
            }
            result.add(tempList);
        }
        
        return result;
    }
}

或者

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levelTraList = new ArrayList<>();
        if(root == null) {
            return levelTraList;
        }
        
        Queue<Node> nodeQ = new LinkedList<>();
        nodeQ.offer(root);
        
        while(!nodeQ.isEmpty()) {
            Queue<Node> nextNodeQ = new LinkedList<>();
            List<Integer> oneLevel = new ArrayList<>();
            
            while(!nodeQ.isEmpty()) {
                Node node = nodeQ.poll();
                oneLevel.add(node.val);
                for(Node cd : node.children) {
                    nextNodeQ.offer(cd);
                }
            }
            nodeQ = nextNodeQ;
            levelTraList.add(oneLevel);
        }
        
        return levelTraList;
    }
}