L102 Binary Tree Level Order Traversal

BFS

Problem

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7]

Solution

1. BFS TC: O(n) SC: O(n)

public <List<List<TreeNode>> levelOrder(TreeNode root){
    List<List<TreeNode>> res = new ArrayList<>();
    if(root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size;
        List<TreeNode> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            list.add(node);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        res.add(list);
    }
    return res;
}

2. return all the node value most right;

public <List<List<TreeNode>> levelOrder(TreeNode root){
    List<List<TreeNode>> res = new ArrayList<>();
    if(root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size;
        List<TreeNode> list = new ArrayList<>();
        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);
            if(i == size -1 ) list.add(node);////////
        }
        res.add(list);
    }
    return res;
}