C ++中二叉树的对角遍历？
考虑在坡度-1的线之间通过的节点。二叉树的对角线遍历将遍历并打印这些行之间存在的所有那些节点。
让我们首先定义一个结构，该结构将表示一个包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来我们创建我们的createNode(intdata)该函数接受一个int值并将其分配给该节点的数据成员。该函数将指针返回到创建的结构节点。同样，新创建的节点的左和右子级设置为null。
struct Node* newNode(int data){
struct Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}traverseDiagonal（Node*根，int深度，map<int，vector<int>>＆myMap）函数将我们的根节点，当前深度以及以int值作为键并将int的向量作为值的映射。我们将myMap作为对此函数的引用。然后该函数检查root是否为null，如果不是，则在执行顺序遍历时，将元素root->data推入当前深度的矢量数据结构的后面。
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
if(root){
m[depth].push_back(root->data);然后，我们对树进行递归有序遍历，以跟踪对角线距离，并在遍历树的左子节点时将深度加1。遍历树的右子节点时，我们不会向深度添加任何内容。
traverseDiagonal(root->leftChild, depth+1, myMap); traverseDiagonal(root->rightChild, depth, myMap);
接下来，在主要功能中，我们使用createNode(data)功能。
Node *root = createNode(10); root->leftChild = createNode(5); root->rightChild = createNode(15); root->leftChild->leftChild = createNode(4); root->leftChild->rightChild = createNode(6); root->rightChild->rightChild = createNode(17); root->rightChild->rightChild->leftChild = createNode(16);
然后，我们声明一个映射myMap，其中包含int作为键，int的向量作为值。然后将此映射与根节点和当前深度一起传递到traverseDiagonal。
map<int, vector<int>> myMap; traverseDiagonal(root, 0, myMap);
在映射myMap中填充值之后，我们使用基于循环的范围对其进行迭代并打印那些对角线值。
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}示例
让我们看一下下面的实现，找到二叉树的对角线遍历。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node{
int data;
Node *leftChild, *rightChild;
};
Node* createNode(int data){
Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
if(root){
m[depth].push_back(root->data);
traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);
}
}
int main(){
Node *root = createNode(10);
root->leftChild = createNode(5);
root->rightChild = createNode(15);
root->leftChild->leftChild = createNode(4);
root->leftChild->rightChild = createNode(6);
root->rightChild->rightChild = createNode(17);
root->rightChild->rightChild->leftChild = createNode(16);
map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}
}输出结果上面的代码将产生以下输出-
10 15 17 5 6 16 4