请用c++给出二叉树的自下而上,从右到左的层次遍历算法的完整代码
时间: 2024-06-08 18:12:30 浏览: 82
使用 C++ 实现二叉树层次遍历的示例代码
以下是二叉树的自下而上,从右到左的层次遍历算法的完整代码:
```c++
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) q.push(node->right);
}
res.push_back(level);
}
stack<vector<int>> st;
for (int i = res.size() - 1; i >= 0; i--) {
st.push(res[i]);
}
vector<vector<int>> ans;
while (!st.empty()) {
ans.push_back(st.top());
st.pop();
}
return ans;
}
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
vector<vector<int>> res = levelOrderBottom(root);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
其中,`levelOrderBottom`函数表示二叉树的自下而上,从右到左的层次遍历。首先使用队列进行常规的层次遍历,然后将结果存储到一个二维数组`res`中。接下来,将`res`数组中的所有元素按照从后往前的顺序依次压入栈中,最后将栈中的元素依次弹出,存储到另一个二维数组`ans`中,即为最终结果。
阅读全文