题目:

107. 二叉树的层次遍历 II

题解:

就比第102题多了一句:

Collections.reverse(list);

代码:

1. 迭代法:


/** * code107 */

import java.util.*;

public class code107 {

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // 将根节点放入队列中,然后不断遍历队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 获取当前队列的长度,这个长度相当于,当前这一层的节点个数
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            // 将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
            // 如果节点的左/右子树不为空,也放入队列中
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if (t.left != null) {
                    queue.offer(t.left);
                }
                if (t.right != null) {
                    queue.offer(t.right);
                }
            }
            // 将临时list加入最终返回结果中
            res.add(tmp);
        }
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println("***************************************");
        Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
        TreeNode tree = ConstructTree.constructTree(nums);
        TreeOperation.show(tree);
        System.out.println("***************************************");
        List<List<Integer>> list = levelOrderBottom(tree);
        System.out.println(list.toString());
        System.out.println("***************************************");
    }
}

2. 递归法:


/** * code107 */

import java.util.*;

public class code107 {

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        // 用来存放最终结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(1, root, res);
        Collections.reverse(res);
        return res;
    }

    public static void dfs(int index, TreeNode root, List<List<Integer>> res) {
        // 假设res是[ [1],[2,3] ], index是3,就再插入一个空list放到res中,index表示当前的层数
        if (res.size() < index) {
            res.add(new ArrayList<Integer>());
        }
        // 将当前节点的值加入到res中,index代表当前层,假设index是3,节点值是99
        // res是[ [1],[2,3] [4] ],加入后res就变为 [ [1],[2,3] [4,99] ]
        res.get(index - 1).add(root.val);
        // 递归的处理左子树,右子树,同时将层数index+1
        if (root.left != null) {
            dfs(index + 1, root.left, res);
        }
        if (root.right != null) {
            dfs(index + 1, root.right, res);
        }
    }

    public static void main(String[] args) {
        System.out.println("***************************************");
        Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
        TreeNode tree = ConstructTree.constructTree(nums);
        TreeOperation.show(tree);
        System.out.println("***************************************");
        List<List<Integer>> list = levelOrderBottom(tree);
        System.out.println(list.toString());
        System.out.println("***************************************");
    }
}

注:

参考:

  1. dfs和bfs两种方法简单实现层次遍历
  2. java实现:思路同自顶向下层次遍历
  3. 详细通俗的思路分析,多解法
  4. 107二叉树的层次遍历II(队列法和递归法)
  5. 递归和非递归两种解法
  6. 迭代 和 递归
  7. Java反转一个List或ArrayList
  8. Java反转一个List或ArrayList
  9. Java 实例 - 集合反转
  10. java - 反转ArrayList的最简单方法是什么?
  11. Java List.add添加元素
  12. Java中的LinkedList的方法的应用