自底向上二叉树层序遍历

“二叉树的层序遍历 II”是一道关于算法的题目，主要涉及数据结构中的二叉树和队列的应用，通常出现在IT技术面试或编程竞赛中。 在计算机科学中，二叉树是一种特殊的树结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。层序遍历（Level Order Traversal）是二叉树的一种遍历方式，按照从上至下、从左至右的顺序访问所有节点。而在本题中，要求的是自底向上的层序遍历，即从最底层的叶子节点开始，逐层向上直到根节点。 给出的参考答案是用C++实现的解决方案。首先定义了一个名为`Solution`的类，其中包含一个名为`levelOrderBottom`的成员函数，该函数接收一个`TreeNode`类型的指针`root`作为参数，表示二叉树的根节点。 在函数内部，定义了一个二维整型向量`levelOrder`用于存储结果，初始化为空。如果输入的根节点为空，直接返回空的结果。然后，使用一个`queue`（队列）来辅助进行层次遍历，将根节点入队。 进入主循环，只要队列不为空，就持续处理当前层的节点。首先创建一个一维向量`level`来存储当前层的所有节点值，然后获取当前层的节点数量`size`。接下来，通过一个for循环遍历当前层的所有节点，依次出队并将其值添加到`level`中，同时将它们的左右子节点入队。完成一层的处理后，将`level`加入到结果向量`levelOrder`中。 最后，由于我们希望自底向上的顺序，所以需要反转`levelOrder`。这可以通过调用`std::reverse`函数实现，它会将`levelOrder`的元素顺序反转，使得最后一层（最初入队的叶子节点层）成为第一个元素。 这个算法的时间复杂度是O(n)，其中n是二叉树中的节点数，因为它需要访问每个节点一次。空间复杂度也是O(n)，最坏情况下队列可能需要存储所有节点。这种解决方案有效地利用了队列的先进先出特性，实现了二叉树的层次遍历，并且符合题目要求的自底向上输出。