層遍歷問題

問題：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).

Input:

• 樹的跟 :: TreeNode

Output:

• 整棵樹的按層遍歷：List<List<Integer>>

Intuition:

這個題可以做BFS的例題了，就醬...

Code:

TC:O()

public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> res = new ArrayList<>();
  if (root == null){
    return res;
  }
  Deque<TreeNode> que = new ArrayDeque<>();
  que.offer(root);

  while (!que.isEmpty()){
    List<Integer> list = new ArrayList<>();
    int size = que.size();
    for(int i = 0; i < size; i++){ //nodes in one level
      ListNode cur = que.poll();
      list.add(cur.val);
      if (cur.left != null){
        que.offer(cur.left);
      }
      if (cur.right != null){
        que.offer(cur.right);
      }
    }  
    res.add(list);
  }
  return res;
}

問題：Binary Tree Level Order Traversal II

列遍歷問題

之型遍歷問題

問題：Binary Tree Zigzag Level Order Traversal

Reference: