首页 > 试题广场 >

求二叉树的层序遍历

[编程题]求二叉树的层序遍历
  • 热度指数:239666 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)
例如:
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]


提示:
0 <= 二叉树的结点数 <= 1500


示例1

输入

{1,2}

输出

[[1],[2]]
示例2

输入

{1,2,3,4,#,#,5}

输出

[[1],[2,3],[4,5]]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
from queue import Queue
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        lst_level = []
        if not root:
            return lst_level
        # 创建一个FIFO队列
        q = Queue()
        # 根节点入队
        q.put(root)
        # 遍历所有结点,即队列非空
        while not q.empty():
            # row保存当前层的结点
            row = []
            # 当前层对应的节点数
            n = q.qsize()
            # 循环出队当前层结点并将孩子结点入队
            for i in range(n):
                # 出队结点
                node = q.get()
                # 出队结点值添加至row队列
                row.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            # 当前层结点遍历完毕
            lst_level.append(row)
        return lst_level

发表于 2022-07-21 17:28:38 回复(0)
Python3
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        queue = [(root, 0)]
        res = []
        while queue:
            r, n = queue.pop(0)
            if r == None:
                continue
            if len(res) - 1 != n:
                res.append([r.val])
            else:
                res[n].append(r.val)
            queue.append((r.left, n + 1))
            queue.append((r.right, n + 1))
        return res


发表于 2022-06-21 11:09:41 回复(0)
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#

# @param root TreeNode类 
# @return int整型二维数组
#
# 队列
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if not root:
            return []
        Max_order = -999
        l_Sort =[]
        q_Layers = [root] # 存放队列节点
        q_order = [0] # 存顺序
        while len(q_Layers) > 0:
            TempRoot = q_Layers.pop(0) # 取出队列第一个值
            order = q_order.pop(0) # 取出当前序号
            # 新层级则创建新的子列表
            if order > Max_order:
                Max_order = order
                l_Sort.append([])
            l_Sort[order].append(TempRoot.val) # 子列表添加数据
            # 若root子节点不为空
            if TempRoot.left or TempRoot.right:
                if TempRoot.left:
                    q_Layers.append(TempRoot.left)
                    q_order.append(order + 1)
                if TempRoot.right:
                    q_Layers.append(TempRoot.right)
                    q_order.append(order + 1)
        return l_Sort
发表于 2022-03-07 11:30:26 回复(0)
import java.util.*;

public class Solution {
    //使用两个队列循环实现,该方法同样可解之字形二叉树遍历
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        Queue<TreeNode> q=new LinkedList<>();//队列q
        Queue<TreeNode> p=new LinkedList<>();//队列p
        q.add(root);//root 进入队列q
        ArrayList<Integer> al=null;
        //两个队列有一个不为空作为循环条件,都空跳出循环
        while(!q.isEmpty() || !p.isEmpty()){
            //q不空 al指向新数组列表用来存q中对应节点值
            if(!q.isEmpty()) al=new ArrayList<>();
            else break;
            //遍历q队列,将节点依次存入p队列
            while(!q.isEmpty()){
                TreeNode node=q.poll();
                if(node.left!=null) p.add(node.left);
                if(node.right!=null) p.add(node.right);
                //将节点值依次全部存入al数组列表,直到q空
                al.add(node.val);
            }
            //将al存入list;
            list.add(al);
            //p不空 al指向新数组列表用来存p中对应节点值
            if(!p.isEmpty()) al=new ArrayList<>();
            else break;
            //遍历p队列,将节点依次存入q队列
            while(!p.isEmpty()){
                TreeNode node=p.poll();
                if(node.left!=null) q.add(node.left);
                if(node.right!=null) q.add(node.right);
                //将节点值依次全部存入al数组列表,直到p空
                al.add(node.val);
            }
            //将al存入list;
            list.add(al);
        }
        return list;
    }
}

发表于 2021-11-08 18:38:54 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = deque.pollFirst();
                curLevel.add(curNode.val);
                if (curNode.left != null) {
                    deque.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    deque.addLast(curNode.right);
                }
            }
            ans.add(curLevel);
        }
        return ans;
    }
}

发表于 2021-10-03 18:27:17 回复(0)
/**
     * 使用队列来解决,先进先出
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return res;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            //确定层数 第一层1个、第二层2个
            int len=queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }

发表于 2021-08-03 22:12:47 回复(0)
//采用双循环 两个队列完成遍历
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        if(root==null)
            return new ArrayList(new ArrayList());
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Queue<TreeNode> t=new LinkedList<>();
            while(!q.isEmpty())
                t.add(q.poll());
            ArrayList<Integer> abs=new ArrayList<>();
            while(!t.isEmpty()){
                TreeNode node=t.poll();
                abs.add(node.val);
                if(node.left!=null)
                    q.add(node.left);
                if(node.right!=null)
                    q.add(node.right);
            }
            ans.add(abs);
        }
        return ans;
    }
}

发表于 2021-07-19 23:32:10 回复(0)
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        //一定要注意这句,不加就是空指针异常
        if(root!=null){
        Queue<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            ArrayList<Integer> list2=new ArrayList<>();
            int size=qu.size();
            while(size>0){
                TreeNode cur=qu.poll();
                list2.add(cur.val);
                size--;
                 if(cur.left!=null){
                    qu.offer(cur.left);
                }
                if(cur.right!=null){
                     qu.offer(cur.right);
                 }
            }
            list.add(list2);
        }
        }
        return list;
    }

发表于 2021-05-31 00:26:26 回复(0)
二叉树的遍历可以考虑递归实现,其中层次遍历与其二叉树深度有关,所以可以设计一个深度计数器,每次递归时计数器加1。
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        DFS(root,res,0);
        return res;
    }
    public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
        if(root == null) return;
        if(list.size() == depth) list.add(new ArrayList<>());
        DFS(root.left, list, depth + 1);
        list.get(depth).add(root.val);
        DFS(root.right, list, depth + 1);
    }

发表于 2021-04-16 10:31:45 回复(0)
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
    // write code here
    let res=[];
    if(!root){
        return [];
    }
    function tra(node,depth){
        if(!res[depth]){
            res[depth]=[];
        }
        res[depth].push(node.val);
        if(node.left){
            tra(node.left,depth+1);
        }
        if(node.right){
            tra(node.right,depth+1);
        }
    }
    tra(root,0);
    return res;
}
module.exports = {
    levelOrder : levelOrder
};

发表于 2021-04-06 16:37:45 回复(0)
function levelOrder( root ) {
    const res = [];
    if (!root) return res;
    const queue = [root];
    while (queue.length > 0) {
        res.push(queue.map(i => i.val));
        let len = queue.length;
        while (len) {
            const cur = queue.shift();
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
            len--;
        }
    }
    return res;
}

发表于 2021-04-02 17:10:59 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    /*基本思想:使用2个变量记录当前层还未打印节点的数量以及下一层需要打印节点的数量*/
    /*其他思路:1)while里面嵌套for循环,for循环的大小为当前层的大小
              2)采用2个队列,还有一个队列用于保存当前的层数*/
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(root == null)
            return res;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.addLast(root);
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        int num = 1;      // 当前层还需打印的节点数量
        int ans = 0;      // 下一层累加的节点数量
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeFirst();
            --num;
            tmp.add(cur.val);
            if(cur.left != null){
                queue.add(cur.left);
                ++ans;
            }           
            if(cur.right != null){
                queue.add(cur.right);
                ++ans;   
            }
            if(num == 0){
                res.add(tmp);
                tmp = new ArrayList<Integer>();
                num = ans;
                ans = 0;
            }
        }
        return res;
    }
}

发表于 2021-04-01 23:52:01 回复(0)
思路:
    一层一层的去遍历

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();  //存答案
        if(root==null) return res;
        ArrayList<TreeNode> level=new ArrayList<>();  //用来存当前的树的层
        level.add(root);
        
        while(!level.isEmpty()){
            ArrayList<TreeNode> tmp = new ArrayList<>(); //创建临时的层,用来存放下一层
            ArrayList<Integer> resLevel= new ArrayList<>(); //用来存放当前层的结果
            for(TreeNode node:level){
                resLevel.add(node.val); //将当前层的结果塞进去
                if(node.left!= null) tmp.add(node.left);    //同时看当前层的左右孩子,存进tmp
                if(node.right!=null) tmp.add(node.right);
            }
            level=tmp;     //用tmp覆盖当前层,下一轮循环将是下一层了
            res.add(resLevel); //别忘了存放当前层的结果。
        }
        return res;
    }
}


发表于 2021-01-22 01:03:21 回复(0)

层序遍历思路就是借助队列的特性来实现
整体思路为
节点入队,队列不为空循环,出队则打印,并顺序入队左右子节点。
需要把层分出来有两种思路:
借助 Map 存储每个节点层数(已知根节点为 1)
不借助 Map 当前层最后节点,和下一层最后节点(已知跟节点为当前层最后节点)
算法如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrderWithMap (TreeNode root) {
           // write code here

        Queue<TreeNode> queue=new LinkedList<>();
        Map<TreeNode,Integer> levelMap=new HashMap<>(16);
        ArrayList<ArrayList<Integer>> result=new ArrayList<>(16);
        if(root==null){
            return result;
        }
        levelMap.put(root,1);
        int currentLevel=1;
        ArrayList<Integer> currentLevelNodesArray=new ArrayList<>(16);
        result.add(currentLevelNodesArray);
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode treeNode=queue.poll();
            //获取当前出队节点level
            int currentNodeLevel=levelMap.get(treeNode);
            System.out.println(treeNode.val);
            if (treeNode.left!=null){
                levelMap.put(treeNode.left,currentNodeLevel+1);
                queue.add(treeNode.left);
            }
            if (treeNode.right!=null){
                levelMap.put(treeNode.right,currentNodeLevel+1);
                queue.add(treeNode.right);
            }
            if (currentLevel!=currentNodeLevel){
                //已经是下一层生成新列表
                currentLevel++;
                currentLevelNodesArray=new ArrayList<>(16);
                result.add(currentLevelNodesArray);
            }
            currentLevelNodesArray.add(treeNode.val);
        }

        return result;
    }

     /**
     * 不借助 map 解法
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here

        Queue<TreeNode> queue=new LinkedList<>();

        ArrayList<ArrayList<Integer>> result=new ArrayList<>(16);
        if(root==null){
            return result;
        }
        //记录当前层最后一个节点,整个算法是基于我已知根节点是第一层最后一个节点
        TreeNode currentEndNode=root;
        //记录下一层最后一个节点
        TreeNode nextEndNode=null;

        ArrayList<Integer> currentLevelNodesArray=new ArrayList<>(16);
        result.add(currentLevelNodesArray);
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode curNode=queue.poll();
            //获取当前出队节点level
            if (curNode.left!=null){
                queue.add(curNode.left);
                //如果有左节点更新下一层最后节点
                nextEndNode=curNode.left;
            }
            if (curNode.right!=null){
                queue.add(curNode.right);
                nextEndNode=curNode.right;
            }
            //不由分说先入队
            currentLevelNodesArray.add(curNode.val);
            //如果当前出队节点是当前层最后一个节点
            //生成新列表 更新当前层最后节点
            if (curNode==currentEndNode){
                //已经是下一层生成新列表
                currentLevelNodesArray=new ArrayList<>(16);
                result.add(currentLevelNodesArray);
                currentEndNode=nextEndNode;
            }
        }
        result.remove(result.size()-1);

        return result;
    }
}
发表于 2020-11-28 10:32:13 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        ArrayList<Integer> list;
        if(root != null) {
            q1.add(root);
        }
        TreeNode node;
        // 每一层作为一次循环,q1作为奇数层的节点存储;q2作为偶数层的节点存储
        while(q1.size() > 0 || q2.size() > 0) {
            list = new ArrayList<Integer>();
            while(q1.size() > 0) {
                node = q1.poll();
                list.add(node.val);
                if(node.left != null) {
                    q2.add(node.left);
                }
                if(node.right != null) {
                    q2.add(node.right);
                }
            }
            if(list.size() > 0) {
                result.add(list);
            }
            
            list = new ArrayList<Integer>();
            while(q2.size() > 0) {
                node = q2.poll();
                list.add(node.val);
                if(node.left != null) {
                    q1.add(node.left);
                }
                if(node.right != null) {
                    q1.add(node.right);
                }
            }
            if(list.size() > 0) {
                result.add(list);
            }
        }
        return result;
    }
}

发表于 2020-11-15 22:52:12 回复(0)
package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
*/
func levelOrder( root *TreeNode ) [][]int {
    // write code here
    ret := make([][]int, 0)
    tmp := make([]int, 0)
    nodeList := make([]*TreeNode, 0)

    if root == nil {
        return ret
    }
    nodeList = append(nodeList, root)
    for i, listLen := 0, len(nodeList); i<listLen; {
        tmp = append(tmp, nodeList[i].Val)
        if nodeList[i].Left != nil {
            nodeList = append(nodeList, nodeList[i].Left)
        }
        if nodeList[i].Right != nil {
            nodeList = append(nodeList, nodeList[i].Right)
        }
        if i == listLen - 1 {
            ret = append(ret, tmp)
            tmp = tmp[len(tmp):]
            nodeList = nodeList[listLen:]
            i = 0
            listLen = len(nodeList)
        } else {
            i++
        }
    }
    return ret
}

解题思路:
1、使用一个Slice(上面代码中的nodeList)充当队列的作用,每次将每层的节点入队,每层的节点入队完后在出队将出队的节点的值追加到同一个一维的int类型的Slice,然后将这个临时的Slice追加到int类型的二维Slice。
2、注意上面代码中的nodeList,提前计算了队列长度,所以知道当前层有几个节点,所有后续当前层的左右孩子节点可以继续追加到该队列中,使用完当前层的所有节点后,再统一出队(删除),如此循环。
发表于 2020-08-21 18:22:38 回复(0)
//java 层序遍历 
//感觉已经程序化了,就是维护一个队列 入队出子树入队子树出队,出队的时候记得进入临时数组
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //判空
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }

        //建一个二维的List和一个用来BFS的queue(用LinkedList实现)
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点放入队列中,然后不断遍历队列
        queue.add(root);
        while(queue.size()>0) {//只要队列非空 就循环
            //获取当前队列的长度,这个长度相当于 当前这一层的节点个数
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            //将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
            //如果节点的左/右子树不为空,也放入队列中
            for(int i=0;i<size;++i) {
                TreeNode t = queue.remove();
                tmp.add(t.val);
                if(t.left!=null) {
                    queue.add(t.left);
                }
                if(t.right!=null) {
                    queue.add(t.right);
                }
            }
            //将临时list加入最终返回结果中
            res.add(tmp);
        }
        return res;
    }
}

发表于 2020-07-12 15:53:13 回复(1)
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > orders;
        if(root == NULL)
            return orders;
        int level = 1; 
        queue<TreeNode *> q1,q2;
        q1.push(root);
        while(!q1.empty() || !q2.empty()){
            if(level % 2 == 1){
                vector<int> res;
                while(!q1.empty()){
                    TreeNode *p = q1.front();
                    res.push_back(p->val);
                    q1.pop();
                    if(p->left)
                        q2.push(p->left);
                    if(p->right)
                        q2.push(p->right);
                }
                orders.push_back(res);
                level++;
            }
            else{
                vector<int> res;
                while(!q2.empty()){
                    TreeNode *p = q2.front();
                    res.push_back(p->val);
                    q2.pop();
                    if(p->left)
                        q1.push(p->left);
                    if(p->right)
                        q1.push(p->right);
                }
                orders.push_back(res);
                level++;
            }
        }
        return orders;
    }
};

发表于 2020-04-27 12:41:28 回复(0)
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        queue.add(root);
        TreeNode cur = root;
        TreeNode last = root;
        TreeNode nLast = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                nLast = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nLast = cur.right;
            }
            list.add(cur.val);
            if (cur == last) {
                lists.add(list);
                list = new ArrayList<>();
                last = nLast;
            }
        }
        return lists;
    }
}
发表于 2019-11-05 17:26:52 回复(0)
import java.util.ArrayList;


public class Solution {

    /**
     * 递归的方式实现
     */
    public ArrayList<ArrayList<Integer>> levelOrder1(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (root == null)
            return result;

        recursionHelper(result, 0, root);
        return result;
    }

    private void recursionHelper(ArrayList<ArrayList<Integer>> result, int level, TreeNode root) {
        if (root == null)
            return;

        // 遍历新的行
        if (level == result.size()) {
            ArrayList<Integer> levelResult = new ArrayList<>();
            levelResult.add(root.val);
            result.add(levelResult);
        } else {    // 已经遍历过的 level 行
            ArrayList<Integer> levelResult = result.get(level);
            levelResult.add(root.val);
            result.set(level, levelResult);
        }
        // 遍历下一行
        recursionHelper(result, level + 1, root.left);
        recursionHelper(result, level + 1, root.right);
    }

    /**
     *  非递归的方式,遍历当前层同时保存对应的左右节点
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (root == null)
            return result;

        ArrayList<TreeNode> curLevel = new ArrayList<>();
        curLevel.add(root);

        while (!curLevel.isEmpty()) {
            // 当前层的遍历结果
            ArrayList<Integer> curResult = new ArrayList<>();
            // 保存下一层的节点
            ArrayList<TreeNode> nextLevel = new ArrayList<>();
            for (TreeNode node : curLevel) {
                curResult.add(node.val);
                if (node.left != null)
                    nextLevel.add(node.left);

                if (node.right != null)
                    nextLevel.add(node.right);
            }
            result.add(curResult);
            curLevel = nextLevel;
        }
        return result;
    }
}
发表于 2018-07-19 18:08:21 回复(0)