题目链接
Minimum Depth of Binary Tree - LeetCode
注意点
- 不要访问空结点
解法
解法一：递归，DFS。首先判空，若当前结点不存在，直接返回0。然后看若左子结点不存在，那么对右子结点调用递归函数，并加1返回。反之，若右子结点不存在，那么对左子结点调用递归函数，并加1返回。若左右子结点都存在，则分别对左右子结点调用递归函数，将二者中的较小值加1返回即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
if(!root->left) return 1+minDepth(root->right);
if(!root->right) return 1+minDepth(root->left);
return 1+min(minDepth(root->left),minDepth(root->right));
}
};
解法二：非递归，BFS层序遍历，记录遍历的层数，一旦我们遍历到第一个叶结点，就将当前层数返回，即为二叉树的最小深度。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int ret = 0;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
ret++;
for(int i = q.size();i > 0;i--)
{
auto n = q.front();q.pop();
if(!n->left && !n->right) return ret;
if(n->left) q.push(n->left);
if(n->right) q.push(n->right);
}
}
return -1;
}
};
