阅读 96

LeetCode 二叉树的层次遍历

第102题


给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal

复制代码

如何遍历一棵树

有两种通用的遍历树的策略:

  • 深度优先搜索(DFS)

在这个策略中,我们采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支。

深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为先序遍历,中序遍历和后序遍历。

  • 宽度优先搜索(BFS)

我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。

解题思路

方法 1:迭代+队列

我们将树上顶点按照层次依次放入队列结构中,队列中元素满足 FIFO(先进先出)的原则。使用 Queue 接口中的 LinkedList实现。

算法实现如下:

  • 初始化队列只包含一个节点 root。
  • 初始一个List变量result,用来做返回结果 当队列非空的时候,循环开始:
  • 计算当前层有多少个元素:等于队列的长度
  • 初始一个List变量subResult,用来存当前层的节点值
  • 将这些元素从队列中弹出,将他们的值加入subResult列表中
  • 将他们的孩子节点作为下一层压入队列中
  • 进入下一层,将当前层subResult add到result中
/**
 * 广搜+队列
 */
class Solution102_1 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        return BFS(root);
    }

    List<List<Integer>> BFS(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> result = new LinkedList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> subResult = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                subResult.add(node.val);
            }
            result.add(subResult);
        }
        return result;
    }
}
复制代码

方法 2:递归

首先确认树非空,然后调用递归函数 DFS(node,result,level),参数是当前节点、返回结果列表、节点的层次。

算法实现如下:

  • result列表的长度小于level,为result add一个新列表
  • 为当前层的result列表add节点值,即result.get(level - 1).add(node.val)
  • 如果有左孩子,调用DFS(node.left, result, level + 1),进入递归
  • 如果有右孩子,调用DFS(node.right, result, level + 1),进入递归
/**
 * 深搜+递归
 */
class Solution102_2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> result = new LinkedList<>();

        DFS(root, result, 1);
        return result;
    }

    void DFS(TreeNode node, List<List<Integer>> result, int level) {
        if (result.size() < level) {
            result.add(new LinkedList<>());
        }
        result.get(level - 1).add(node.val);
        if (node.left != null) {
            DFS(node.left, result, level + 1);
        }
        if (node.right != null) {
            DFS(node.right, result, level + 1);
        }
    }
}
复制代码

完整代码

public class Sub102 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        Solution102_2 solution = new Solution102_2();
        List<List<Integer>> list = solution.levelOrder(root);
        for (List<Integer> subList : list) {
            System.out.println(subList.toString());
        }
    }
}

/**
 * 广搜+队列
 */
class Solution102_1 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        return BFS(root);
    }

    List<List<Integer>> BFS(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> result = new LinkedList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> subResult = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                subResult.add(node.val);
            }
            result.add(subResult);
        }
        return result;
    }
}

/**
 * 深搜+递归
 */
class Solution102_2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> result = new LinkedList<>();

        DFS(root, result, 1);
        return result;
    }

    void DFS(TreeNode node, List<List<Integer>> result, int level) {
        if (result.size() < level) {
            result.add(new LinkedList<>());
        }
        result.get(level - 1).add(node.val);
        if (node.left != null) {
            DFS(node.left, result, level + 1);
        }
        if (node.right != null) {
            DFS(node.right, result, level + 1);
        }
    }
}
复制代码

资料

关注下面的标签,发现更多相似文章
评论