102. Binary Tree Level Order Traversal

题目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]
]

1,递归(dfs)

 public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(root,result,0);
        return result;
    }
    
    private void dfs(TreeNode root,List<List<Integer>> result,int level){
        if(root == null){
            return;
        }
        
        if(level >= result.size()){
            result.add(new ArrayList<Integer>());
        }
        
        result.get(level).add(root.val);
        dfs(root.left,result, level+1);
        dfs(root.right,result,level+1);
       
    }

2,递归(bfs)

 public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null){
            return result;
        }
        
        List<TreeNode> levelNodes = new ArrayList<TreeNode>();
        levelNodes.add(root);
        bfs(levelNodes,result);
        return result;
    }
    
    private void bfs(List<TreeNode> levelNodes ,List<List<Integer>> result){
        if(levelNodes.isEmpty()){
            return;
        }
        List<Integer> levelResult = new ArrayList<Integer>();
        List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
        for(int i=0, len=levelNodes.size(); i<len; i++){
            TreeNode node = levelNodes.get(i);
            levelResult.add(node.val);
            if(node.left != null){
                nextLevelNodes.add(node.left);
            }
             if(node.right != null){
                nextLevelNodes.add(node.right);
            }
        }
        result.add(levelResult);
        bfs(nextLevelNodes,result);
    }

3,非递归

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null){
            return result;
        }
        //存储当前层节点
        List<TreeNode> curLevelNodes = new ArrayList<TreeNode>();
        curLevelNodes.add(root);
        
        while(!curLevelNodes.isEmpty()){
            //存储下一层的节点
             List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
             List<Integer> levelResult = new ArrayList<Integer>();
             for(TreeNode node : curLevelNodes){
                 levelResult.add(node.val);
                 if(node.left != null){
                     nextLevelNodes.add(node.left);
                 }
                 if(node.right != null){
                     nextLevelNodes.add(node.right);
                 }
             }
             result.add(levelResult);
            curLevelNodes = nextLevelNodes;
        }
        return result;
    }