leetcode——107.二叉树的层次遍历II

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            LinkedList<Integer> subList = new LinkedList<>();
            int sz = q.size();
            for(int i = 0;i<sz;i++){
                TreeNode cur = q.poll();
                subList.offer(cur.val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            res.offerFirst(subList);
        }
        return res;
    }

BFS。

DFS如下：

private LinkedList<List<Integer>> ans;
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        ans = new LinkedList<>();
        getOrder(root,1);
        return ans;
    }

    private void getOrder(TreeNode root, int level) {
        if(root== null){
            return;
        }
        if(ans.size() < level){
            ans.addFirst(new LinkedList<Integer>());
        }
        List<Integer> subList = ans.get(ans.size() - level);
        subList.add(root.val);
        getOrder(root.left, level+1);
        getOrder(root.right,level+1);
    }

 ——2020.6.30