【LeetCode】107.二叉树的层序遍历II


1.问题

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:

"图1"

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

2.解题思路

其实与【LeetCode】102.二叉树的层序遍历广度优先的思路没啥大的区别,从结果来看,就是结果集逆序输出,只要我们在遍历每层完成后,将临时结果集按照头插法插入结果集即可。可以利用List.add(index,value)的方法完成头插法。

3.代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //分层遍历,利用队列思想,头插法
        if(null == root){
            return new ArrayList();
        }
        //结果集
        List<List<Integer>> res=new ArrayList();
        //每层的结果集
        List<Integer> tempList=new ArrayList();
        List<TreeNode> temp=new ArrayList<TreeNode>();
        //根节点入队
        temp.add(root);
        temp.add(null);
        TreeNode node;
        while(!temp.isEmpty()){
            node=temp.remove(0);
            if(null != node){
                tempList.add(node.val);
                if(null!=node.left){
                    temp.add(node.left);
                }
                if(null!=node.right){
                    temp.add(node.right);
                }
            } 
            //本层已遍历完毕
            else if(!tempList.isEmpty()){
                //头插法(与102不同的地方)
                res.add(0, tempList);
                tempList=new ArrayList();
                temp.add(null);
            }
        }
        return res;
    }
}

文章作者: Kezade
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kezade !
评论
  目录