Leetcode-102-Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

leetcode: https://leetcode.com/problems/binary-tree-level-order-traversal/

Description:

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Idea:

use array list to store the result. use queue to record elements of each layer.

Step1: if the node is null, add it to queue.

Step2: create the list and record the size of the queue, pop all elements of the queue to the list firstly(get this layers’ elements). create a node to record each poped node of the queue. then verify this temporary node’s left and right child is equal to null or not, if the node has child, then add child to the queue.

Step3: store the list of this layer’e element to the array.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //create list array to store the result
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //if root is null, the tree is empty
        if(root == null){
            return result;
        }
        //create the queue to record elements of each layer
        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        //record the root
        queue.offer(root);
        
        //when the queue is empty, it means the last element has been visited
        while(!queue.isEmpty()){
            //create list to record the all elements of current layer
            List<Integer> Lay_list = new ArrayList<Integer>();

            //to record this layer's size
            int size = queue.size();
            
            //get each element of this layer, and add next layer's elements to the queue
            for(int i=0; i<size; i++){
                //use temporay node to record each node of this layer
                TreeNode temp = queue.poll();

                //get current layer's elements
                Lay_list.add(temp.val);

                //get next layer's elements through each node of current layer
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
            //store the each layer to the result list
            result.add(Lay_list);
        }
        return result;
    }
}