1. 首页
  2. LeetCode

每日一道 LeetCode (23):二叉树的层次遍历 II

每日一道 LeetCode (23):二叉树的层次遍历 II

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:二叉树的层次遍历 II

题目来源:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

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

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

    3
   / \
  9  20
    /  \
   15   7

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

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

解题思路

看到这道题,如果还有不会做的同学,可能需要受到马桶搋子的教育。

这道题和昨天的那道题基本上是同一道题,昨天的那道题是一个顺序遍历,这道题是一个逆序遍历。

顺序遍历使用的是队列的结构,逆序遍历能想到啥?

当然是栈啊,队列是先进先出的数据结构,而栈是一个先进后出的数据结构。

在使用栈的时候只要按照循序把元素一个一个放进去放好,最后再拿出来直接就是一个逆序的结构,完全不需要多余的处理的好么。

解法一:使用栈

这个解法就是把昨天的代码上加上一个栈,在每次循环的时候把元素放到栈里,最后迭代一次栈,将栈中的元素输出后返回。

// 顺序思维操作 耗时 2ms
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    if (root == null) return new ArrayList<>();

    List<List<Integer>> result = new ArrayList<>();

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

    // 新增一个数据结构,栈
    Stack<List<Integer>> stack = new Stack<>();

    // 外层循环,每次循环都是一层
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        // 循环这一层的所有节点
        while (size > 0) {
            TreeNode node = queue.poll();
            // 将这一层的所有节点放到 list 中
            list.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            size--;
        }
        // 将列表当道栈中
        stack.push(list);
    }

    // 将栈中数据取出来放到列表中
    while (!stack.isEmpty()) {
        result.add(stack.pop());
    }

    return result;
}

每日一道 LeetCode (23):二叉树的层次遍历 II

这段代码稍微有点长,不过很好理解,完全的顺序思维。

不知道你们发现没有,越长的代码越容易看懂,越短的代码理解起来越费劲,就比如昨天的那个递归的方法,总共就两行,想看懂还是有点难度的。

解法二:使用 List 代替栈

上面的解法耗时稍微有点长,我们需要先把数据赛到栈里,然后再迭代整个栈把元素逆序输出,那么能不能优化一下呢?

当然可以,我们可以不适用栈,直接使用列表的 List.add(int index,E element) 这个方法,这个方法不懂的建议直接度娘。

// 优化代码,不适用栈,直接使用 list.add 方法,耗时 1ms
public List<List<Integer>> levelOrderBottom_1(TreeNode root) {
    List<List<Integer>> result = new LinkedList<>();
    if (root == null) return result;

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

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            size--;
        }
        result.add(0, list);
    }
    return result;
}

每日一道 LeetCode (23):二叉树的层次遍历 II

这段代码没有加注释,和上面那段基本一样,只是单纯的去掉了栈,在循环中使用 result.add(0, list); 将元素放入列表中,从而实现逆序列表的输出。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code