关注Java领域相关技术 记录有趣的事情

LeetCode-107. 二叉树的层次遍历 II

US-B.Ralph
US-B.Ralph
2020-09-06

问题地址

LeetCode每日一题/2020-09-06

LeetCode107. 二叉树的层次遍历 II

问题描述

规则

  • 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

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

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

解析

解题思路

  • 使用递归逐层遍历；
    • 当前节点为空则直接返回；
    • 当前节点无子节点时直接返回；
  • 遍历过程中，使用map存储每一层的元素，key为深度，value为当前深度的所有元素；

数据操作分析

复杂度分析

  1. 时间复杂度，O(N^2)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次。
  2. 空间复杂度，O(N^2)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。

编码实现

/**
 * LeetCode107
 */
public class LeetCode0107_BinaryTreeLlevelOrderTraversalii {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        Integer depth = 0;
        List<List<Integer>> result = new ArrayList<>();
        recursive(root, depth, map);
        for (int i = map.size() - 1; i >= 0; i--) {
            result.add(map.get(i));
        }

        return result;
    }

    private void recursive(TreeNode root, Integer depth, Map<Integer, List<Integer>> map) {
        if (root == null) return;
        List<Integer> list;
        if (map.get(depth) == null) {
            list = new ArrayList<>();
        } else {
            list = map.get(depth);
        }
        list.add(root.val);
        map.put(depth, list);
        if (root.left == null && root.right == null) {
            return;
        } else {
            depth++;
            recursive(root.left, depth, map);
            recursive(root.right, depth, map);
        }
    }
}

官方解法

前言

这道题和「102. 二叉树的层序遍历」相似，不同之处在于，第 102 题要求从上到下输出每一层的节点值，而这道题要求从下到上输出每一层的节点值。除了输出顺序不同以外，这两道题的思路是相同的，都可以使用广度优先搜索进行层次遍历。

广度优先搜索

思路：

  • 树的层次遍历可以使用广度优先搜索实现。从根节点开始搜索，每次遍历同一层的全部节点，使用一个列表存储该层的节点值。
  • 如果要求从上到下输出每一层的节点值，做法是很直观的，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的尾部。这道题要求从下到上输出每一层的节点值，只要对上述操作稍作修改即可：在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。
  • 为了降低在结果列表的头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构，在链表头部添加一层节点值的列表的时间复杂度是 O(1)。在 Java 中，由于我们需要返回的 List 是一个接口，这里可以使用链表实现；而 C++ 或 Python 中，我们需要返回一个 vector 或 list，它不方便在头部插入元素（会增加时间开销），所以我们可以先用尾部插入的方法得到从上到下的层次遍历列表，然后再进行反转。

复杂度分析：

  1. 时间复杂度，O(n)，其中 n 是二叉树中的节点个数。每个节点访问一次，结果列表使用链表的结构时，在结果列表头部添加一层节点值的列表的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
  2. 空间复杂度，O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。

编码实现

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }
}

精彩评论

跳转地址：三种实现+图解 107.二叉树的层次遍历 II

BFS实现

  • BFS遍历比较直观，就是按层遍历

实现思路

  • 我们将我们一层遍历得到的结果放到一个数组中，等这一层遍历完后，将这个数组放入到最终结果集res中。因为题目要求是反序输出，所以我们只需将res翻转一下就可以了。
    • 我们看下如何实现这个BFS遍历
    • 如上图，首先创建一个队列，将根节点root放入队列中，然后不断循环遍历这个队列。
      对于树的第一层，其长度为1，而此时根节点也放到队列中了，所以队列的长度也是1，我们取出一个元素，将其放入临时数组中。
    • 如果这个节点的左右孩子不为空，则将他们也放入队列中。
    • 上图是处理第二层的过程，类似于第一层，由于第一层遍历完后，队列里有两个元素了，所以第二次遍历的时候，可以确定队列长度是2，于是执行两次，将2和3取出，放入临时数组中，之后再将2和3的两个孩子也放入队列中。
    • 处理第三层时，队列长度就是4了，于是取出4个元素，再次处理。

编码实现

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //用来存放最终结果
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        //创建一个队列，将根节点放入其中
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            //每次遍历的数量为队列的长度
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            //将这一层的元素全部取出，放入到临时数组中，如果节点的左右孩子不为空，继续放入队列
            for(int i=0;i<size;++i) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right!=null) {
                    queue.offer(node.right);
                }
            }
            res.add(tmp);
        }
        //翻转最终结果并返回
        Collections.reverse(res);
        return res;
    }
}

BFS实现2

  • 第一种方式中，我们将最终结果集定义成数组，等所有元素都放置完后，再翻转一下数组。
    我们可以将其结构改成链表，以后每层遍历完将结果放入到链表的第一位，这样就自动完成了翻转的功能了。

编码实现

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //改用链表实现，每次都插入到第一位
        LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            for(int i=0;i<size;++i) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right!=null) {
                    queue.offer(node.right);
                }
            }
            //每次都保存到链表的第一位，这样自带了翻转的功能
            res.add(0,tmp);
        }
        return res;
    }
}

DFS实现

实现思路

  • DFS实现就不那么直观了，我们可以把二叉树结构改变一下，想象成一个三角形的结构
  • 我们在递归遍历时，将第一层的元素放入到第一层的数组中，将第二层的的元素放入到第二层，第三层的元素放入第三层。
  • 第三层的4是在5之前被遍历的，所以放入到第三层数组时，4就在5前面，同理6是在7前面被遍历的，所以放入到第三层时6就在7前面。

  • 这次我们不用创建队列了，直接在最终结果集res上操作，res是个二维数组，集合中嵌套集合，但现在没有任何嵌套的集合。

  • 如上图所示，

    • 一开始res是空的，当遍历到第一层时候，我们创建一个集合，放入res，然后将第一层的1，放到res[0]中。
    • 遍历到第二层时，再创建一个集合放入res，然后将2放入res[1]中。
    • 遍历到第三层时，同样再创建一个集合放入res，将4放入res[2]中。
    • 当我们再回到第三层，遍历到5时，就不用再创建新集合了，直接将5放到到res[2]中即可。
      之后，再将3放到res[1]；6、7放入res[2]中。
  • 完整的遍历过程如下图：
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //用来存放最终结果
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(root,res,1);
        Collections.reverse(res);
        return res;
    }

    private void dfs(TreeNode root,ArrayList<List<Integer>> res,int index) {
        if(root==null) {
            return;
        }
        //如果index大于res大小，说明这一层没有对应的集合，需要新创建
        if(index>res.size()) {
            res.add(new ArrayList<Integer>());
        }
        //将当前层的元素直接放到对应层的末尾即可
        res.get(index-1).add(root.val);
        //继续遍历左右节点，同时将层高+1
        dfs(root.left,res,index+1);
        dfs(root.right,res,index+1);
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

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

5 × 2 =