深圳市做网站,网站搭建团队,做设计用哪个素材网站,wordpress例一、题目描述
给你二叉树的根节点 root #xff0c;返回其节点值 自底向上的层序遍历 。 #xff08;即按从叶子节点所在层到根节点所在的层#xff0c;逐层从左向右遍历#xff09; 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;[…一、题目描述
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 示例 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
二、解题思路 这个问题是关于如何对二叉树进行自底向上的层序遍历。我们可以使用一个队列来进行广度优先搜索BFS并使用一个变量来记录当前层的节点值。在遍历每一层的时候我们使用一个双端队列Deque来存储当前层的节点值这样我们就可以从双端队列的尾部开始遍历从而实现自底向上的层序遍历。
算法步骤
初始化一个空队列queue用于BFS以及一个空的双端队列deque用于存储当前层的节点值。如果root不为空则将其加入queue。初始化一个变量level为0用于标识当前层的奇偶性。当queue不为空时进行以下操作 a. 获取当前层的节点数量size即queue的长度。 b. 遍历当前层的节点对于每个节点 i. 从queue中移除节点并将其值加入deque的头部如果level为偶数或尾部如果level为奇数。 ii. 如果该节点的左子节点不为空将其加入queue。 iii. 如果该节点的右子节点不为空将其加入queue。 c. 将deque转换为列表并加入结果列表result。 d. 将level加1清空deque。返回结果列表result。
三、具体代码
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}QueueTreeNode queue new LinkedList();queue.offer(root);int level 0;while (!queue.isEmpty()) {int size queue.size();DequeInteger deque new LinkedList();for (int i 0; i size; i) {TreeNode node queue.poll();if (node ! null) {deque.offerLast(node.val);queue.offer(node.left);queue.offer(node.right);}}if (!deque.isEmpty()) {result.add(0, new ArrayList(deque));}}return result;}
}四、时间复杂度和空间复杂度
1. 时间复杂度
levelOrderBottom 函数会对每个节点进行一次操作其中 n 是树中节点的数量。因此总的时间复杂度是 O(n)。
2. 空间复杂度
空间复杂度主要取决于队列和双端队列中存储的节点数量。在最坏的情况下树是完全不平衡的例如每个节点都只有左子节点或者只有右子节点此时队列和双端队列中存储的节点数量最多为 O(n)。因此总的空间复杂度是 O(n)。
综上所述代码的时间复杂度是 O(n)空间复杂度也是 O(n)其中 n 是树中节点的数量。
五、总结知识点 队列Queue的使用代码中使用了LinkedList类作为Queue的实现用于在BFS中存储待遍历的节点。队列遵循先进先出FIFO的原则。 递归虽然代码中没有直接使用递归但BFS本质上是一种递归的过程通过循环模拟递归的调用栈。 双端队列Deque的使用代码中使用了LinkedList类作为Deque的实现用于在每一层遍历时存储当前层的节点值。双端队列可以同时从两端添加或删除元素。 迭代与循环使用while循环来迭代遍历树的每一层直到队列为空。 条件语句使用if-else语句来判断节点是否为空以及判断队列是否为空。 数据结构转换使用ArrayList和LinkedList之间的转换将Deque中的元素转换为一个List然后添加到结果List中。 布尔变量的使用使用布尔变量level来标志当前层的奇偶性并在每层遍历后取反。 树节点的定义代码中使用了TreeNode类来定义二叉树的节点每个节点包含一个整数值和指向左右子节点的引用。 函数返回值levelOrderBottom函数返回一个包含多层的ListListInteger表示二叉树的自底向上的层序遍历结果。 边界条件的处理在函数开始时检查root是否为空如果为空则直接返回一个空列表。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
