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

题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],

3    / \   9  20     /  \    15   7

返回其层次遍历结果：

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

题解

我想用栈来实现，但是发现有些问题。日后再补充。

现在，干脆就直接学习学习他人的优秀算法，顺便记录一下感想。

该算法题解来自~

微信公众号：看图学算法

链接：https://mp.weixin.qq.com/s/oI_pmqvaA9AFQUPxKX13vw

用广度优先BFS处理是很直观的，可以想象成是一把刀横着切割了每一层，但是深度优先遍历就不那么直观了。

我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子。

田字形的每一层就对应一个list。

按照深度优先DFS的处理顺序，会先访问节点1，再访问节点2，接着是节点3。

之后是第二列的4和5，最后是第三列的6。 每次递归的时候都需要带一个index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的list不存在，就加入一个空list进去。

动态演示如下：

代码

import java.util.*;	class Solution {
       void dfs(int index,TreeNode root, List
   
    
     > res) {
           //每次递归的时候都需要带一个index(表示当前的层数)        //如果当前行对应的list不存在，就加入一个空list进去。		//假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中		if(res.size()
     
      ());		}		//将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99		//res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]		res.get(index-1).add(root.val);		//递归的处理左子树，右子树，同时将层数index+1		if(root.left!=null) {
   			dfs(index+1, root.left, res);		}		if(root.right!=null) {
   			dfs(index+1, root.right, res);		}	}	public List
      
       
        > levelOrder(TreeNode root) {
   		if(root==null) {
   			return new ArrayList
        
         
          >(); } //用来存放最终结果 List
          
           
            > res = new ArrayList
            
             
              >(); dfs(1,root,res); return res; } }
             
            
           
          
         
        
       
      
     
    
   

时间复杂度:**O(N)

空间复杂度:O(h)，h是树的高度

心得体会

首先，我绝对不会想到用list，因为我对集合一是不敏感，二是基础知识掌握不多。

第二点是，灵活性的不足，即使我想不到list，但是我也没想过“我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子”🤣 先前写算法基本都是用C来写，偶尔用C++。 有的题目用C写起来轻松，但是有的却用Java轻松。 很必要的一点，就是学会使用两种及以上的语言来写算法。

其他题解

---

图片来源：微信公众号“看图学算法”

学习笔记，待补充…

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