关注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 中,我们需要返回一个 vectorlist,它不方便在头部插入元素(会增加时间开销),所以我们可以先用尾部插入的方法得到从上到下的层次遍历列表,然后再进行反转。

复杂度分析:

  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

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