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 协议》，转载必须注明作者和本文链接