c++ 图论2 深度优先算法和广度优先算法

修改一下深度优先算法和广度优先算法，标出每一个节点相对于遍历起始位置的层级，遍历起始起点为第一层，和第一层相连的节点为第二层，以此类推

定义一个新的结构

struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(TreeNode* n, int l) : node(n), level(l) {}
};

深度优先搜索（DFS）

class Solution {
public:vector<NodeWithLevel> dfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;dfsHelper(root, 1, result);return result;}private:void dfsHelper(TreeNode* node, int level, vector<NodeWithLevel>& result) {if (node == nullptr) {return;}// 将当前节点及其层级添加到结果中result.push_back(NodeWithLevel(node, level));// 递归处理左子树，层级加1dfsHelper(node->left, level + 1, result);// 递归处理右子树，层级加1dfsHelper(node->right, level + 1, result);}
};

DFS算法的工作原理：

1. 我们使用一个辅助函数 dfsHelper，它接受当前节点、当前层级和结果vector作为参数。
2. 如果当前节点为空，我们直接返回。
3. 我们将当前节点和其层级添加到结果中。
4. 然后我们递归地处理左子树和右子树，每次递归时层级加1。

广度优先搜索（BFS）: 

class Solution {
public:vector<NodeWithLevel> bfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;if (root == nullptr) {return result;}queue<NodeWithLevel> q;q.push(NodeWithLevel(root, 1));while (!q.empty()) {NodeWithLevel current = q.front();q.pop();// 将当前节点及其层级添加到结果中result.push_back(current);// 如果左子节点存在，将其加入队列，层级加1if (current.node->left) {q.push(NodeWithLevel(current.node->left, current.level + 1));}// 如果右子节点存在，将其加入队列，层级加1if (current.node->right) {q.push(NodeWithLevel(current.node->right, current.level + 1));}}return result;}
};

这个BFS算法的工作原理：

1. 我们创建一个队列来存储 NodeWithLevel 对象。
2. 我们从根节点开始，将其作为第一层加入队列。
3. 当队列不为空时，我们取出队首元素，将其添加到结果中。
4. 然后我们检查当前节点的左右子节点，如果存在，就将它们加入队列，层级为当前节点的层级加1。
5. 重复这个过程直到队列为空。

这两种算法都会返回一个 vector<NodeWithLevel>，其中包含了树中所有节点及其对应的层级。DFS 通常会以前序遍历的顺序返回节点，而 BFS 会按照层序遍历的顺序返回节点。