DFS(深度搜索) & BFS(广度搜索)

前言

遍历二叉树我们会经常用到BFS和DFS,这里记录下两种方式的区别。

例题

输入一棵二叉树求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

这里获取一棵二叉树的深度，可以是递归的方法，属于DFS（深度优先搜索）；另一种方法是按照层次遍历，属于BFS（广度优先搜索）。

DFS(深度搜索)

• 通过遍历的方式进行深度搜索
• 可以是自底向上汇总搜索结果 or 自顶向下汇总搜索结果

示例代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    // 自底向上搜索
    int DFS1(TreeNode* root) {
      if (root == nullptr) {
        return 0;
      }
      int left = DFS1(root->left);
      int right = DFS1(root->right);

      return left > right ? left + 1 : right + 1;
  }

 // 自顶向下搜索
int depthRes = 0;
void DFS2(TreeNode* root,int depth) {
    if (root == nullptr) {
        return;
    }
    depth = depth + 1;
    if(depth > depthRes) {
        depthRes = depth;
    }
    DFS2(root->left, depth);
    DFS2(root->right, depth);
}


};

BFS(广度搜索)

• 广度搜索一般通过 队列queue 来帮助完成（queue 有着先进先出的特性）

示例代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
// 广度搜索
int BFS(TreeNode* root)
{
    if (root == nullptr) {
        return 0;
    }
    queue<TreeNode*> treeQueue;
    int resDepth = 0;
    treeQueue.push(root);
    while (treeQueue.size()) {
        int size = treeQueue.size();
        resDepth ++;
        for (int i = 0; i < size; ++i) {
            TreeNode* tmp = treeQueue.front();
            treeQueue.pop();
            if (tmp->left != nullptr) {
                treeQueue.push(tmp->left);
            }
            if (tmp->right != nullptr) {
                treeQueue.push(tmp->right);
            }
        }
    }
    return resDepth;
}

}

记录下，深度搜索 和 广度搜索的方案。
end！