力扣第102题-二叉树的层序遍历 前言 一、思路 二、实现

发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

前言

力扣第102题 二叉树的层序遍历 如下所示：

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],

1
2
3
4
5
markdown复制代码    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

1
2
3
4
5
csharp复制代码[
  [3],
  [9,20],
  [15,7]
]

一、思路

题目中就一个要求：返回层序遍历结果

既然要按树的深度（层数）从左至右获取结果，所以我们至少要知道一个信息：当前层数有多少个节点。而当前层数的节点，是由前面的节点决定的。

所以我们需要在遍历当前的节点时，将不为空 null 的左孩子和右孩子加入下一层节点 nextLevel，提供给下一次遍历。

综上所述，实现的步骤只需要两步：

  1. 遍历当前层的节点，将节点值加入到当前层结果集，并依次将各节点不为空的 左孩子 和 右孩子 加入到下一层的节点
  2. 只要下一层节点不为空，则重复第一步的过程

举个例子

在这里我们可以使用 递归 或者 遍历 来实现，这两种实现代码都会在实现代码中给出示例。在这里我们使用 递归 来举个例子：

一些变量说明：

List<TreeNode> currentLevel：当前层的不为空的节点
List<TreeNode> nextLevel：下一层不为空的节点
List<Integer> temp：当前层的结果集

以示例中的 [3,9,20,null,null,15,7] 作为例子

  1. 根节点不为空，遍历第一层节点 currentLevel = [3]，可获得结果集 temp = [3]，再将左孩子右孩子加入下一层节点 nextLevel = [9, 20]
  2. 遍历第二层 currentLevel = [9, 20]，可获得结果集 temp = [9, 20]，再将他们的左孩子和右孩子加入下一层节点 nextLevel = [15, 7]
  3. 遍历第三层 currentLevel = [15, 7]，可获得节点集 temp = [15, 7]。当前层节点中都没有左右孩子了，故结束遍历
  4. 返回结果 ret = [[3], [9, 20], [15, 7]] 即可

二、实现

实现代码

实现代码与思路中保持一致，下方为递归和遍历两种实现方式

递归

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
java复制代码List<List<Integer>> ret = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root!=null) {
        dfs(Collections.singletonList(root));
    }
    return ret;
}

public void dfs(List<TreeNode> currentLevel) {
    if (currentLevel.size() < 1)
        return;
    List<Integer> temp = new ArrayList<>();
    List<TreeNode> nextLevel = new ArrayList<>();
    // 遍历当前层级
    for (TreeNode treeNode : currentLevel){
        temp.add(treeNode.val);
        if (treeNode.left != null){
            nextLevel.add(treeNode.left);
        }
        if (treeNode.right != null){
            nextLevel.add(treeNode.right);
        }
    }
    ret.add(temp);
    dfs(nextLevel);
}

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码public List<List<Integer>> levelOrder1(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    if (root == null) {
        return ret;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        int currentLevelSize = queue.size();
        for (int i = 1; i <= currentLevelSize; ++i) {
            TreeNode node = queue.poll();
            temp.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        ret.add(temp);
    }
    return ret;
}

测试代码

1
2
3
4
5
6
java复制代码public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(3,
            new TreeNode(9),
            new TreeNode(20, new TreeNode(15), new TreeNode(7)));
    new Number102().levelOrder(treeNode);
}

结果

image.png

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%