二叉树的后序遍历
（力扣145题)
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
**输入：**root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
**输入：**root = []
输出：[]
示例 4：
**输入：**root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
**进阶：**递归算法很简单，你可以通过迭代算法完成吗？
- 栈的使用：利用栈保存节点，从根节点开始，依次将节点压入栈中。
- 模拟遍历顺序：后序遍历的顺序是“左 - 右 - 根”，但栈是后进先出，因此先压入左子节点，再压入右子节点，这样弹出时就是“根 - 右 - 左”的顺序。
- 反转结果：由于栈的弹出顺序与后序遍历相反，最后将结果数组反转，即可得到正确的后序遍历顺序。
- 循环条件：当栈不为空时，继续弹出节点并处理其子节点，直到栈为空为止。
这种方法通过栈模拟了递归的处理过程，避免了递归的函数调用栈开销，同时通过反转结果数组巧妙地实现了后序遍历的顺序。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
// 后序遍历
vector<int> postorderTraversal(TreeNode *root)
{
// 定义栈
stack<TreeNode *> st;
// 结果集
vector<int> result;
// 空节点 返回空
if (root == NULL)
{
return result;
}
// 根节点压入栈
st.push(root);
while (!st.empty())
{
TreeNode *node = st.top(); // 根节点
st.pop();
result.push_back(node->val);
if (node->left)
{
// 左（空节点不入栈
st.push(node->left);
}
if (node->right)
{
// 右（空节点不入栈
st.push(node->right);
}
}
// 反转结果集
reverse(result.begin(), result.end());
return result;
}
};
二叉树的 层序遍历
（力扣102题)
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000解题思路
- 队列辅助：使用队列存储待访问的节点。队列先进先出的特点适合逐层访问二叉树。
- 初始化：如果根节点不为空，将其加入队列。
- 逐层遍历：当队列不为空时，每次处理一层的节点。通过队列的大小（
que.size()）确定当前层的节点数。 - 处理当前层：逐个弹出当前层的节点，将其值加入当前层的向量
vec。同时，将每个节点的左、右子节点（如果存在）依次加入队列，为下一层的遍历做准备。 - 存储结果：将当前层的节点值向量
vec添加到结果向量result中。 - 循环结束：当队列为空时，所有层的节点都已遍历完成，返回结果向量
result。
这种方法通过队列逐层处理节点，确保了层序遍历的顺序，同时利用队列的大小来区分每一层，简洁高效。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
// 定义一个队列que，用于存储待访问的节点
queue<TreeNode*> que;
// 如果根节点root不为空，将根节点加入队列
if(root != NULL)
{
que.push(root);
}
// 定义一个二维向量result，用于存储层序遍历的结果
vector<vector<int>>result;
// 当队列不为空时，继续遍历
while(!que.empty())
{
// / 获取当前队列的大小，即当前层的节点数
int size = que.size();
// 定义一个向量vec，用于存储当前层的节点值
vector <int>vec;
while(size--)
{
// 获取队列的第一个节点
TreeNode *node = que.front();
// 将该节点从队列中移除
que.pop();
// 将该节点的值添加到当前层的向量vec中
vec.push_back(node->val);
// 如果该节点有左子节点，将左子节点加入队列
if(node->left)
{
que.push(node->left);
}
// 如果该节点有右子节点，将右子节点加入队列
if(node->right)
{
que.push(node->right);
}
}
// 将当前层的节点值向量vec添加到结果向量result中
result.push_back(vec);
}
// 返回层序遍历的结果
return result;
}
};
二叉树的层次遍历 II
（力扣107题)
给你二叉树的根节点 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
解题思路
- 队列辅助遍历：使用队列存储待访问的节点，按照层序遍历的顺序逐层处理节点。
- 逐层处理：每次处理一层时，根据队列的大小（
que.size()）确定当前层的节点数，依次弹出当前层的节点，将其值加入到当前层的向量vec中。 - 加入子节点：对于每个弹出的节点，将其左子节点和右子节点（如果存在）依次加入队列，为下一层的遍历做准备。
- 存储当前层结果：将当前层的节点值向量
vec添加到结果向量result中。 - 反转结果：由于层序遍历是从上到下进行的，而题目要求从下到上存储结果，因此在遍历结束后，将结果向量
result反转。 - 返回结果：最终返回反转后的结果向量
result，即从底部向上存储的层序遍历结果。
这种方法利用队列实现了层序遍历的逐层处理，并通过反转结果向量巧妙地满足了题目要求的从下到上的存储顺序。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue <TreeNode*> que;
if(root != NULL)
{
que.push(root);
}
vector<vector<int>> result;
while(!que.empty())
{
// 获取当前层大小
int size = que.size();
vector<int> vec;
// 获取当前层的所有元素并加入容器
while(size--)
{
TreeNode *node = que.front();
que.pop();
vec.push_back(node->val);
// 有左子树加入到队列中
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
result.push_back(vec);
}
reverse(result.begin(), result.end());
return result;
}
};