树的非常规遍历问题(cont)

层遍历问题

问题: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:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容