第107题：二叉树的层次遍历II

一．问题描述

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

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

/ \

9 20

/ \

15 7

返回其自底向上的层次遍历为：

[

[15,7],

[9,20],

[3]

]

二．解题思路

本题思路：采用层序遍历和递归的方法进行求解。

步骤一：构建递归函数（全局变量list表存储结果数据，局部表data存储当前一层所有节点）

步骤二：对data表进行遍历，将其子树存储在newdata表中，并进行递归（list，newdata）。

步骤三：当在最底层时，将newdata节点数存储在list表中，并返回上一层接着存储，直到结束。

步骤四：返回list表。

三．执行结果

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

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

四． Java代码

class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> list=new ArrayList<List<Integer>>();

        if(root==null) {

            return list;

        }else {

            List<TreeNode> data=new ArrayList<TreeNode>();

            data.add(root);

            getTree(list,data);

            return list;

        }

    }

    public void getTree(List<List<Integer>> list,List<TreeNode> data) {

        if(data.size()==0) {

            return ;

        }

     List<TreeNode> newdata=new ArrayList<TreeNode>();

     List<Integer> temp=new ArrayList<Integer>();

     for(int i=0;i<data.size();i++) {

         if(data.get(i).left!=null) {

             newdata.add(data.get(i).left);

         }

         if(data.get(i).right!=null) {

             newdata.add(data.get(i).right);

         }

         temp.add(data.get(i).val);

     }

     getTree(list, newdata);

     list.add(temp);

    }

}

巴特西

第107题：二叉树的层次遍历II

最新文章

热门文章