广度优先(BFS)

广度优先(BFS) 1 广度优先简介

常常使用队列来配合解决。

2 力扣题目 2.1 二叉树的最小深度

111. 二叉树的最小深度

迭代版本：

class Solution {
public:
    int minDepth(TreeNode* root) {
		if (!root)
		{
			return 0;
		}

		queue q;
		q.push(root);
		//root本身就是一层,所以初始化为1
		int minDep = 1;
		while (!q.empty())
		{
			int sz = q.size();
			//将当前队列中的所有节点向四周扩散
			for (int i = 0;i < sz; ++i)
			{
				TreeNode *cur = q.front();
				q.pop();
				//判断是否到达终点
				if (!cur->left && !cur->right)
				{
					return minDep;
				}

				//将cur相邻的节点加入队列
				if (cur->left)
				{
					q.push(cur->left);
				}

				if (cur->right)
				{
					q.push(cur->right);
				}
			}
			//这里增加步数
			++minDep;
		}

		return minDep;    
    }
};

递归版本：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root)
        {
            return 0;
        }

        if (!root->left)
        {
            return 1 + minDepth(root->right);
        }
        else if (!root->right)
        {
            return 1 + minDepth(root->left);
        }
        else
        {
            return 1 + std::min(minDepth(root->left), minDepth(root->right));
        }       
    }
};

2.2