本文共 1387 字，大约阅读时间需要 4 分钟。

题目

思路1（迭代）

• BFS广度优先搜索
• 用队列先进先出特性遍历

代码

class Solution {    public List
   
    
     > levelOrder(TreeNode root) {        List
     
      
       > res = new LinkedList<>();        if (root == null) {            return res;        }        Deque
       
         queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            List
        
          level = new LinkedList<>(); int size = queue.size(); while (size > 0) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } size--; } res.add(level); } return res; }}
        
       
      
     
    
   

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(N)\)

思路2（递归）

• DFS深度优先搜索
• res.size() < index：每一层只能添加一个链表用来存储本层节点的值
• 每次搜索遍历都将本节点添加道对应的层的位置

代码

class Solution {    public List
   
    
     > levelOrder(TreeNode root) {        List
     
      
       > res = new LinkedList<>();        if (root == null) {            return res;        }        dfs(1, res, root);        return res;    }    public void dfs(int index, List
       
        
         > res, TreeNode root) { if (root == null) { return; } // 每层只能添加一个链表 if (res.size() < index) { res.add(new LinkedList<>()); } // 将节点的值添加道本层的链表中 res.get(index-1).add(root.val); dfs(index+1, res, root.left); dfs(index+1, res, root.right); }}
        
       
      
     
    
   

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(h)\)，其中 h 为树的高度

转载地址：http://lspyz.baihongyu.com/