二分木のジグザグ走査を試みています。しかし、私は1つのタイプのテストケース、つまりツリーのバランスが取れていない場合に行き詰まっています。私が私の入力をとして与えるならば
3
3 9 20 null null 15 7
次のような二分木の場合：
3
/ \
9 20
/ \
15 7
出力が表示されます：
3
20 9
0
入力が39 20 1 null 15 7の場合、出力は3 20 9 10です。
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;
}
私が理解していることから、入力がnullの場合、コードは何も返さず、さらにノードの実行を続行する必要があります。私は自分の間違いを理解することができません。誰か助けてもらえますか？TIA！
コードは実際には、提供されたテストケースで機能するように見えます。入出力に問題があるのではないかと思います。ただし、ソリューション自体は残念ながらそうではありません。次のテストケースについて考えてみます。
1
/ \
5 2
/ \
6 3
/ \
7 4
ソリューションは次のように出力します：[[1]、[5、2]、[6、3]、[7、4]]
ジグザグベクトルの各ベクトルをレベルと呼びましょう。
このアプローチは正しい解決策にたどり着くのが難しいだろうと思います。主にDFSの性質のためです。BFSソリューションが正しい道かもしれません。それは当然、これらのレベルごとのスタイルの問題に適しています。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加