LeetCode-102.Binary Tree Level Order Traversal

发布时间：2020-12-14 04:35:59 所属栏目：大数据来源：网络整理

导读：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,15,7] , 3 / 9 20 / 15 7 return its level order traversal as: [ [3],[9,20],[1

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,15,7],

    3
   /   9  20
    /     15   7

return its level order traversal as:

[
  [3],[9,20],[15,7]
]

重点是如何将每层隔开，使用广度优先遍历，时间复杂度为O(n):

 1  public List<List<Integer>> levelOrder(TreeNode root) {//树 BFS my
 2         Queue<TreeNode> queue = new LinkedList<>();
 3         List<List<Integer>> re = new ArrayList<>();
 4         if(null!=root){
 5             queue.add(root);
 6             queue.add(null);
 7         }
 8         while(!queue.isEmpty()&&null!=queue.peek()){//本方法使用null隔开每一层，也可以记录每一层的个数
 9             List<Integer> list = new ArrayList<>();
10             TreeNode cur = queue.poll();
11             while(null!=cur){
12                 list.add(cur.val);
13                 if(null!=cur.left){
14                     queue.add(cur.left);
15                 }
16                 if(null!=cur.right){
17                     queue.add(cur.right);
18                 }
19                 cur=queue.poll();
20             }
21             queue.add(null);
22             if(!list.isEmpty()){
23                 re.add(list);
24             }
25         }
26         return re;
27     }

也可以使用DFS完成

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!