P33 二叉树的层序遍历

描述#

这个题目说的是，给你一棵二叉树，要求你从根节点到叶子节点一层一层地对其进行访问，对于每一层的节点，则是从左向右进行访问。将访问的结果以二维数组返回。

比如说，给你的二叉树是：
 1

/   

2     4
/ 

8  16
它的层序遍历结果是：
[
[1],
[2, 4],
[8, 16]
]

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public List<List<Integer>> levelOrderTraversal(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      List<Integer> elem = new ArrayList<>();
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        elem.add(s.val);
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      result.add(elem);
    }

    return result;
  }

}