题解 | #求二叉树的层序遍历#

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        if (null == root) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            return result;
        }
        // 定义一个队列
        LinkedList<TreeNode> que = new LinkedList<>();
        // 定义一个辅助节点
        TreeNode tempNode = root;
        
        // 定义一个HashMap，用于存放每个节点对应的层数
        HashMap<TreeNode, Integer> nodeMap = new HashMap<>();
        
        que.add(tempNode);
        
        // 先将root节点添加到HashMap
        nodeMap.put(tempNode, 1);
        
        // 定义一个辅助的ArrayList
        ArrayList<Integer> tempList = null;
        // 定义返回结果
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        
        while (!que.isEmpty()) {
            tempNode = que.poll();
            
            // 具体实现弹出节点的操作
            if (0 == result.size() || nodeMap.get(tempNode) > result.size()) {
                tempList = new ArrayList<>();
                result.add(tempList);
            }
            tempList = result.get(nodeMap.get(tempNode) - 1);
            tempList.add(tempNode.val);
            
            
            if (null != tempNode.left) {
                que.add(tempNode.left);
                nodeMap.put(tempNode.left, nodeMap.get(tempNode) + 1);
            }
            if (null != tempNode.right) {
                que.add(tempNode.right);
                nodeMap.put(tempNode.right, nodeMap.get(tempNode) + 1);
            }
        }
        return result;
    }
}