树相关主要是dfs和bfs，递归万金油
常用结构 stack 和queue
占位，刷完来写总结
【111】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// -BFS
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> que;
que.push(root);
int ans = INT_MAX;
int tree_depth = 1;
while (!que.empty()) {
int len = que.size();
for (int i=0; i<len; i++) {
TreeNode* tmp = que.front();
que.pop();
if (tmp->left == nullptr && tmp->right == nullptr) {
ans = min(ans, tree_depth);
break;
}
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
tree_depth += 1;
}
if (ans<INT_MAX) return ans;
return tree_depth;
}
};
// 递归
class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) return 0;
if (root->left == nullptr && root->right == nullptr) return 1;
if (root->right == nullptr) {
return 1+minDepth(root->left);
}
if (root->left == nullptr) {
return 1+ minDepth(root->right);
}
// 如果两边都不为空
return min(1+minDepth(root->left), 1+minDepth(root->right));
}
};
