102. 二叉树的层次遍历

递推

package leetcode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
class Solution {
    public List> levelOrder(TreeNode root) {
        List> ls = new ArrayList>();
        Queue queue = new LinkedList();
        if (root == null)
            return ls;
        queue.add(root);
        while (!queue.isEmpty()) {                                               // 结合数学运算
            int len = queue.size();
            List l = new ArrayList();
            for (int i = 0; i < len; i++) {                                                        //len用于记录queue.size() 不会被for 里面的代码所影响  这道题 很妙
                TreeNode T = queue.poll();

                if (T.left != null)
                    queue.add(T.left);
                if (T.right != null)
                    queue.add(T.right);
                l.add(T.val);
            }
            ls.add(l);

        }
        return ls;
    }
}

解法二

递归

class Solution {
    public List> levelOrder(TreeNode root) {
        List> list = new ArrayList();
        levelOrder(root, list, 0);
        return list;
    }

    public void levelOrder(TreeNode root, List> list, int level){
        if(root != null){
            if(level > list.size() - 1){
                List nodes = new ArrayList();
                list.add(nodes);
            }
            list.get(level).add(root.val);
            levelOrder(root.left, list, level + 1);
            levelOrder(root.right, list, level + 1);
        }
    }
}