107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如： 给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

思路

102. 二叉树的层序遍历，将其结果逆序返回即可。

解法

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);

        while (!deque.isEmpty()) {
            //获取当前层节点数量
            int len = deque.size();
            List<Integer> list = new ArrayList<>();

            //将该层数据放入result
            while (len > 0 && !deque.isEmpty()) {
                root = deque.poll();
                list.add(root.val);
                if (root.left != null) {
                    deque.offer(root.left);
                }
                if (root.right != null) {
                    deque.offer(root.right);
                }
                len--;
            }
            result.add(list);
        }
        Collections.reverse(result);
        return result;
    }
}