107. Binary Tree Level Order Tra

https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

image.png

（图片来源https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

）

递归

public List<List<Integer>> levelOrderBottom1(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();   // 方便移动
        if(root == null) {
            return result;
        }

        helper(root, result, 0);

        return result;
    }

    private void helper(TreeNode root, List<List<Integer>> result, int level) {

        if(root == null) {
            return;
        }

        if(level >= result.size()) {
            result.add(0, new ArrayList<>());  // 放最前面
        }

        result.get(result.size()- 1 - level).add(root.val); // 增量放在对应层级（size()-1) - level
        if(root.left != null) {
            helper(root.left, result, level+1);
        }
        if(root.right != null) {
            helper(root.right, result, level+1);
        }

    }

非递归

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();  //  方便移动
        if(root == null) {
            return result;
        }

        Queue<TreeNode> nodeQ = new LinkedList<>();
        nodeQ.offer(root);

        while(! nodeQ.isEmpty()) {
            int qLen = nodeQ.size();
            List<Integer> oneLevel = new ArrayList<>();
            for(int i=0; i<qLen; i++) {
                TreeNode node = nodeQ.poll();
                oneLevel.add(node.val);

                if(node.left != null) {
                    nodeQ.offer(node.left);
                }
                if(node.right != null) {
                    nodeQ.offer(node.right);
                }
            }

            result.add(0, oneLevel);  //  增量放在最前面
        }

        return result;
    }