网站数据流分析怎么做百度推广营销

111. 二叉树的最小深度 - 力扣（LeetCode）

注意叶子节点的定义。

因为求的是最小深度，所以可以使用层次遍历（bfs）：

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;int res = 0;queue<pair<TreeNode*, int>> q;q.push({root, 1});while(!q.empty()){TreeNode* p = q.front().first;int val = q.front().second;q.pop();if(!p->left && !p->right){res = val;break;};//叶子节点if(p->left) q.push({p->left, val+1});if(p->right) q.push({p->right, val+1});}return res;}
};

本题只需要求最小深度即可，所有bfs借助的队列可以存储节点即可，我们一次处理二叉树的一层，当碰到叶子节点的时候，就break出来，具体看代码：

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;int res = 1, flag = 1;queue<TreeNode*> q;q.push(root);while(!q.empty()){int len = q.size();for(int i = 0; i < len; ++i){//一次处理一层auto p = q.front();q.pop();if(!p->left && !p->right){//碰到叶子节点flag = 0;break;}   if(p->left) q.push(p->left);if(p->right) q.push(p->right);}if(!flag)   break;//碰到叶子节点++res;//该层没有叶子节点，更新深度}return res;}
};

dfs:

class Solution {
public:int minDepth(TreeNode* root){if (root == nullptr)    return 0;if(!root->left && !root->right) return 1; //叶子节点int min_dep = INT_MAX;if(root->left)  min_dep = min(min_dep, minDepth(root->left));if(root->right)  min_dep = min(min_dep, minDepth(root->right));return 1 + min_dep;}
};