c++学习 图论1

使用c++来写一个bfs和dfs

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 如果根节点为空,树的最小深度为0
        if (root == nullptr) {
            return 0;
        }
        
        // 创建一个队列,用于BFS
        // 队列中的每个元素是一个pair,包含节点指针和该节点的深度
        queue<pair<TreeNode*, int>> q;
        
        // 将根节点加入队列,深度为1
        q.push({root, 1});
        
        // 当队列不为空时,继续搜索
        while (!q.empty()) {
            // 取出队列的前端元素
            auto [node, depth] = q.front();
            q.pop();
            
            // 如果当前节点是叶子节点(没有子节点),返回其深度
            // 这就是最小深度,因为BFS首先到达的叶子节点一定是最浅的
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            
            // 如果左子节点存在,将其加入队列,深度加1
            if (node->left) {
                q.push({node->left, depth + 1});
            }
            // 如果右子节点存在,将其加入队列,深度加1
            if (node->right) {
                q.push({node->right, depth + 1});
            }
        }
        
        // 这行代码实际上不会被执行,因为只要根节点不为空,
        // 我们总会在某个时刻返回一个深度
        return 0;
    }
};

BFS 的核心思想是逐层遍历树,所以它能保证首先找到最小宽度的叶子节点。

现在让我们看看DFS(深度优先搜索)的实现:

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 如果根节点为空,深度为0
        if (root == nullptr) {
            return 0;
        }
        
        // 如果是叶子节点(没有子节点),深度为1
        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }
        
        // 如果左子树为空,只需考虑右子树
        if (root->left == nullptr) {
            return minDepth(root->right) + 1;
        }
        
        // 如果右子树为空,只需考虑左子树
        if (root->right == nullptr) {
            return minDepth(root->left) + 1;
        }
        
        // 如果左右子树都不为空,取两者的较小值
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

DFS 的核心思想是深入地搜索树的分支。在这个例子中,我们可以使用所有可能的路径才能确定最小宽度。

两种方法的比较:

  1. BFS 通常更适合寻找最短路径,因为它是逐层搜索的。在这个问题中,它能找到第一个叶子节点时就停止,这可能导致比 DFS 更快。
  2. DFS的优势在于空间复杂度,特别是在树非常深但不应宽的情况下。它的空间复杂度与树的高度成正比,而BFS的空间复杂度与树的最大宽度成正比。
  3. 从实现角度来看,BFS 通常需要使用额外的数据结构(如队列),而 DFS 则可以直接使用递归,实现起来可能更简洁。
  4. 在处理非常大的树时,BFS可能会因为需要存储大量节点而费内存,而DFS则不可能遇到这个问题。
上一篇:阿里Qwen2-72B大模型已是开源榜的王者,为什么还要推出其他参数模型,被其他模型打榜?


下一篇:华为机试HJ13句子逆序