我正在尝试对二叉树进行之字形遍历。但是我被困在一种类型的测试用例中,即当树不平衡时。如果我将我的输入作为
3
3 9 20 null null 15 7
对于看起来像这样的二叉树:
3
/ \
9 20
/ \
15 7
我得到输出:
3
20 9
0
如果我的输入是 3 9 20 1 null 15 7,我的输出是: 3个 20 9 1 0
下面是我的代码。
struct node
{
int data;
node* left;
node* right;
};
void order (node* root, map <int, vector <int> >& ans, int level, int k) {
if (root == NULL) {
return;
}
if (k==0) {
if (root->left != NULL) {
ans[level+1].push_back(root->left->data);
order (root->left, ans, level+1, 1);
}
if (root->right != NULL) {
ans[level+1].push_back(root->right->data);
order (root->right, ans, level+1, 1);
}
}
else if (k==1) {
order (root->left, ans, level+1, 0);
order (root->right, ans, level+1, 0);
if (root->right != NULL)
ans[level+1].push_back(root->right->data);
if (root->left != NULL)
ans[level+1].push_back(root->left->data);
}
}
vector<vector<int> > zigzag(node* root){
map <int, vector <int> > ans;
vector <vector <int> > zig;
ans[0].push_back(root->data);
order(root, ans, 1, 1);
for (auto it = ans.begin(); it != ans.end(); it++ ) { //converting map into vector
zig.push_back(it->second);
}
return zig;
}
据我所知,如果输入为空,我的代码应该什么都不返回并继续执行更多节点。我无法弄清楚我的错误。有谁能够帮助我? TIA!
最佳答案
您的代码实际上似乎适用于您提供的测试用例。我怀疑你的问题与输入/输出有关。然而不幸的是,解决方案本身不是。考虑以下测试用例:
1
/ \
5 2
/ \
6 3
/ \
7 4
您的解决方案将输出:[[1], [5, 2], [6, 3], [7, 4]]
让我们将之字形 vector 中的每个 vector 称为一个级别。
- 首先,将 1(根)添加到第一层。
- k==1 level==1 然后向左递归。
- k==0 level==2 你正确地将 6 添加到 level 2。然后再次向左递归。
- k==1 level==3 不能左右递归。将 7 错误地加到第 3 级。返回
- k==0 level==2 不能正确递归。返回。
- k==1 level==1 将 5 错误添加到 level 1。向右递归。
- 等等
我认为这种方法很难得到正确的解决方案。主要是因为它的 DFS 性质。 BFS 解决方案可能是正确的路径。它自然适合这些逐级风格的问题。
关于c++ - C++ 中的 ZigZag 二叉树遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50540078/