102. Sequence traversal of binary tree

Sequence traversal ： From left to right , Output the node value of the binary tree from top to bottom .
Force link 102. Sequence traversal of binary tree

Method 1 ： recursive

Element 1 ：

Parameters ：
（1） Traversing nodes TreeNode
（2） The layer number int Used to identify which layer is being traversed
（3）List Node used to store traversal
Return value ： empty

Element 2 ：

The end condition ： Node is empty

Element three ：

Recursive logic ：
If you are traversing the first node of this hierarchy , Building new list Store this layer of data .
Store the node values being traversed .
Go through the next layer ： Recursively traverse its left node , Right node

Concrete realization

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
           List<List<Integer>> lists = new ArrayList<>();
        if(root == null) return lists;
        int level = 1;  
        digui(root,level,lists);
        return lists;
    }

    void digui(TreeNode root,int level,List<List<Integer>> lists){
        if(root == null) return ;
        if(level==lists.size()+1){
            List<Integer> list = new ArrayList(); 
              lists.add(list);  
        }
        lists.get(level-1).add(root.val);
        digui(root.left,level+1,lists);
        digui(root.right,level+1,lists);
    }
}

Method 2 iteration

Implement... With queues , Enter first , Go out first .
Key points ： How to calculate the number of layers ？
1、 Traverse the first layer , Number of layers plus one , Add all child nodes of this layer to the queue .
2、 Traverse all child nodes added in the previous step in the queue , Add their children to the queue . Traverse complete , Number of layers plus one .
3、 Continue with the above steps