第102题：二叉树的层次遍历

一．问题描述

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

例如:

给定二叉树: [3,9,20,null,null,15,7],

9 20

15 7

返回其层次遍历结果：

[

[3],

[9,20],

[15,7]

]

二．解题思路

本题思路：采用递归+广度优先遍历的方法进行求解（创建递归函数（全局变量list存储结果值，临时变量data存储某一层节点））。

步骤一：将根节点加入到data表格中。

步骤二：遍历data节点将其子节点重新填入到新的data中，并将值添加到temp表格中。

步骤三：将temp表添加到list中，并返回步骤二，直到新的data表为空。

步骤四：返回list表。

三．执行结果

执行用时 :2 ms, 在所有 java 提交中击败了65.23%的用户

内存消耗 :36.2 MB, 在所有 java 提交中击败了52.67%的用户

四． Java代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null) {
            return list;
        }
        List<TreeNode> data=new ArrayList<TreeNode>();
        data.add(root);
        Tree(list,data);
        return list;
    }
    
    public void Tree(List<List<Integer>> list,List<TreeNode> data)
    {
        if(data.size()==0)
        {
            return;
        }
        List<TreeNode> temp=new ArrayList<TreeNode>();
        List<Integer> result=new ArrayList<Integer>();
        for(int i=0;i<data.size();i++)
        {
            TreeNode m=data.get(i);
            result.add(m.val);
            
            if(m.left!=null) {
                temp.add(m.left);
            }
            if(m.right!=null) {
                temp.add(m.right);
            }
        }
        list.add(result);
        Tree(list,temp);
    }
}

第102题：二叉树的层次遍历

相关推荐