102. Binary Tree Level Order Traversal

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],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

Straight forward solution:
root node in => left and right children out . -- Lv1
lv 1 nodes in => lv 2 nodes out......
until no more next lv.
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        $q = [];
        $result = [];
        
        if($root === null){
            return $result;
        }
        $q[] = $root;
        while (count($q) > 0){
            $current_level = [];
            $current_result = [];
            foreach ($q as $node){
                if ($node->left !== null) 
                    $current_level[] = $node->left;
                
                $current_result[] = $node->val;
                
                if ($node->right !== null) 
                    $current_level[] = $node->right;
            }
            $q = $current_level;
            $result [] = $current_result;
        }

        return $result;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> r = new ArrayList<>();
        
        if(root == null){
            return r;
        }
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while(!q.isEmpty()){
            
            int sizeSnapshot = q.size();
            List<Integer> current_level = new ArrayList<>();
            
            
            for(int i = 0; i < sizeSnapshot; i ++){
                TreeNode t = q.poll();
                if(t.left != null){
                    q.add(t.left);
                }
                
                current_level.add(t.val);
                
                if(t.right != null){
                    q.add(t.right);
                }
            }
            r.add(current_level);
        }
        
        return r;
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.