LeetCode107-二叉树的层次遍历II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

中文链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

题目详述

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

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

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

题目详解

层次遍历的思路与 LeetCode102-二叉树的层次遍历 是一致的，只不过把层次遍历的顺序由上到下改为了自底向上。在原来层次遍历的基础上，有两种解决方法：

  • 添加一整层的值时从头添加。
  • 直接反转层次遍历的结果链表。

方法一：添加一整层的值时运用 LinkedList 的 addFirst 方法从头添加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class LeetCode_00107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            // 每一层的结点个数
            int size = queue.size();
            // 用来存储这一层结点的链表
            List<Integer> level = new LinkedList<>();
            while (size-- != 0) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 从头添加
            res.addFirst(level);
        }
        return res;
    }
}

方法二：直接反转层次遍历的结果链表。

迭代版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class LeetCode_00107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            while (size-- != 0) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        // 反转
        Collections.reverse(res);
        return res;
    }
}

递归版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traverse(root, 1, res);
        // 反转
        Collections.reverse(res);
        return res;
    }

    private void traverse(TreeNode root, int level, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        if (res.size() < level) {
            res.add(new ArrayList<>());
        }
        res.get(level - 1).add(root.val);
        traverse(root.left, level + 1, res);
        traverse(root.right, level + 1, res);
    }
}