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).

Example1:



Input: Root = [3,9,20, null, null, 15, 7]

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

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Breadth First Search

Java version

The following version of the code is relatively straightforward

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>(); 
        if(root == null) return list; 
        
        // Use an arrayList to install each level Nodes
        ArrayList<TreeNode> nodeList = new ArrayList<TreeNode>(); 
        nodeList.add(root); 
        int level = 0; 
        
        while(! nodeList.isEmpty()) {// Get values of each level nodes
            list.add(new ArrayList<Integer>()); 
            int size = nodeList.size(); 
            for(int i = 0; i < size; i++) {
                list.get(level).add(nodeList.get(i).val); 
            }
            level++; 
            
            ArrayList<TreeNode> temp = new ArrayList<TreeNode>(); 
            for(int i = 0; i < size; i++) {
                TreeNode left = nodeList.get(i).left; 
                TreeNode right = nodeList.get(i).right; 
                if(left ! =null) temp.add(left); 
                if(right ! =null) temp.add(right); 
            }
            nodeList = temp; 
        }
        
        returnlist; }}Copy the code

Depth First Search

Recursion is used when Depth First Search is used to solve the problem. Also, DFS has preorder, inorder, and Postorder, which should all work. Personally, RECURsion is a little more abstract than the BFS above, and you can draw examples to help you write code.

Java version

/** * 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 {
    private static int level = 0; 
    private static List<List<Integer>> list = new ArrayList<List<Integer>>();  
    
    public void preorder(TreeNode node) {
        // base condition of recursion
        if(node == null) return; 
        
        if(list.size() == level) {
            list.add(new ArrayList<Integer>()); 
        }     
        list.get(level).add(node.val); 

        level++; 
        preorder(node.left); 
        preorder(node.right); 
        level--;   
    }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return list; 
        
        list.add(new ArrayList<Integer>()); 
        preorder(root); 
        
        // reset the value of list
        List<List<Integer>> result = list; 
        list = new ArrayList<List<Integer>>(); 
        returnresult; }}Copy the code

The JavaScript version

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /

var level = 0; 
var array = []; 

function preorder(node) {
    if(node === null) return; 
    
    if(array.length === level) 
        array[level] = []; 
    array[level].push(node.val);
    
    level++; 
    preorder(node.left); 
    preorder(node.right); 
    level--; 
}

var levelOrder = function(root) {
    // check if the root is empty 
    if(root === null) {
        return array; 
    }
    / / initialization
    array[level] = []; 
    preorder(root); 
    // reset
    let result = array; 
    array = []; 

    return result; 
};
Copy the code