102. 二叉树的层序遍历

分析

我最开始的想法，是先用中序遍历遍历所有元素（这样，同一层的左边的元素始终排在这一层右边的元素的前面），同时带高度信息，将遍历结果结果放到一个列表里面，然后从头遍历列表，根据节点的高度，来将节点进行分离。
但是官方答案更巧妙，直接使用队列这个数据结构，具体过程如下：

其巧妙的地方在于：

从队列中取出元素的时候，将子元素放到队列中。这个真的很巧妙，这样做，有一种延迟处理的效果。
在开始遍历队列的元素之前，获取队列的长度，当这个长度的元素（属于同一层）遍历完之后，再次更新长度，这样就能将队列中的元素分层
这个题也可以用递归来做，但是没有那么巧妙，还是用队列来做简洁高明。

层序遍历或者说广度优先遍历的本质，就是一层层的遍历。

解题

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    // 先获取从上到下的，然后再反转
    List<List<Integer>> result = new ArrayList<>();
    if(root==null){
        return result;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
	    // 这里一次循环就是遍历一层的节点
        List<Integer> levelVals = new ArrayList<>();
        // 获取这一层的长度
        int length = queue.size();
        // 遍历这一层的每一个节点
        while(length>0){
            TreeNode node = queue.poll();
            levelVals.add(node.val);
            // 移除一个节点的时候，将其子节点放到队列中
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            length--;
        }
        result.add(levelVals);
    }
    return result;
}

102. 二叉树的层序遍历

分析

解题

相关题