102. Binary Tree Level Order Traversal

解法一 Iteration

思路

We can using a queue to store nodes on level. We continue to do a BFS until the queue is empty. A trick here is that , we can denote the length of the root level to be 1. And after searching all the children for a certain level, we denote the size of the queue to be the length of next level.

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

        return levels;
    }
}
复杂度分析
  • 时间复杂度
    Since every node has been visited, the time complexity is O(N).
  • 空间复杂度
    Since every node has been added in the list, the space complexity is O(N).

解法二

思路

Using DFS to traverse one node all the way to the leaf. Add the node to corresponding level list. If the current level hasn't been reached when comparing with levels.size(), we add a new level.

代码
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels  = new ArrayList<>();
        DFS(root, levels, 0);
        return levels;
    }

    public void DFS(TreeNode root, List<List<Integer>> levels, int level) {
        if (root == null) {
            return;
        }
        // We include the equal because the root is 0 level so if we have the level in levels list, the actual level size is level.size() + 1 
        if (levels.size() <= level) {
            levels.add(new ArrayList<Integer>());
        }
        levels.get(level).add(root.val);

        DFS(root.left, levels, level + 1);
        DFS(root.right, levels, level + 1);
    }
}
复杂度分析
  • 时间复杂度
    Since every node has been visited, the time complexity is O(N).
  • 空间复杂度
    Since every node has been added in the list, the space complexity is O(N).

Takeaway

  • Iteration 解法的巧妙之处在于判断了每层节点有几个。
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!