垂直输出二叉树c++
时间: 2023-12-06 12:34:40 浏览: 42
垂直输出二叉树是指按照二叉树节点的垂直位置,将每个垂直位置上的节点值相加并输出。下面是一个C++的实现:
```
#include <iostream>
#include <map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void verticalSum(TreeNode* root, int hd, map<int, int>& m) {
if (root == NULL) {
return;
}
m[hd] += root->val;
verticalSum(root->left, hd - 1, m);
verticalSum(root->right, hd + 1, m);
}
void printVerticalSum(TreeNode* root) {
map<int, int> m;
verticalSum(root, 0, m);
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->second << " ";
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
cout << "Vertical sum of binary tree is: ";
printVerticalSum(root);
return 0;
}
```
这个实现使用了一个map来存储每个垂直位置上的节点值之和。我们从根节点开始遍历二叉树,对于每个节点,我们将其值加到对应垂直位置的map中。然后递归遍历左子树和右子树。最后,我们遍历map并输出每个垂直位置上的节点值之和。