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));
        
        // 递归处理左子树，层级加1
        dfsHelper(node->left, level + 1, result);
        
        // 递归处理右子树，层级加1
        dfsHelper(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);
            
            // 如果左子节点存在，将其加入队列，层级加1
            if (current.node->left) {
                q.push(NodeWithLevel(current.node->left, current.level + 1));
            }
            
            // 如果右子节点存在，将其加入队列，层级加1
            if (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 会按照层序遍历的顺序返回节点。