102. Sequence traversal of binary tree

One 、 Title Description

Give you the root node of the binary tree root , Returns the Sequence traversal . （ That is, layer by layer , Access all nodes from left to right ）.

Example 1：

 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 ：[]

Two 、 Problem solving

BFS

Use breadth first traversal , Then use the queue to save the data of each layer .BFS Better to think about .

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

DFS

Depth-first traversal , Depth of use , Each layer creates a new collection , Then add the data of each layer according to the number of layers of the tree .

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
       //DFS
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
    
            return res;
        }
        dfs(root,0,res);
        return res;
    }
    public void dfs(TreeNode root,int depth,List<List<Integer>> res){
    
        // Jump out of the condition 
        if(root == null){
    
            return;
        }
        // Each layer adds a new set 
        if(depth == res.size()){
    
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        dfs(root.left,depth+1,res);
        dfs(root.right,depth+1,res);      
    }
}