• leetcode题107二叉树的层序遍历-日记篇


    声明:问题描述来源leetcode

    一、问题描述:

    107. 二叉树的层序遍历 II

    难度中等626

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

    示例 1:

    img

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

    示例 2:

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

    示例 3:

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

    提示:

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

    二、题解:

    /**
     * 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 {
        List<List<Integer>> lists = new LinkedList<>();
    
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            if (root == null) return lists;
            lists.add(new LinkedList<>());
            searchGoalByOrder(0,root);
            Collections.reverse(lists);
            return lists;
        }
    
        private void searchGoalByOrder(int order, TreeNode root) {
            lists.get(order).add(root.val);
            if (root.left != null){
                if (order + 1 > lists.size() - 1) lists.add(new LinkedList<>());
                searchGoalByOrder(order + 1,root.left);
            }
    
            if (root.right != null){
                if (order + 1 > lists.size() - 1) lists.add(new LinkedList<>());
                searchGoalByOrder(order + 1,root.right);
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    end

    思路和层序遍历的一样,先按照层序遍历的思路整出一个正序的链表,再通过调用Collections的API来反转该链表。

  • 相关阅读:
    算法基础--位运算
    2023上海工博会,正运动展位现场直击(二)
    Leetcode刷题笔记--Hot61-70
    搭建Eureka高可用集群 - day03
    【MySQL】深入理解MySQL索引优化器工作原理
    快速认识什么是:Docker
    TypeScript - 字符串的字面类型
    RabbitMQ - 02 - 基本消息模型
    Goldengate
    二叉搜索树在线OJ题讲解
  • 原文地址:https://blog.csdn.net/ws_please/article/details/127588327