leetcode111 二叉树的最小深度

相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。

最小深度的定义：从根节点到最近叶子节点的最短路径上的节点数量。

特别注意：

1. 如果一个子树不存在，就不能用它来计算深度（因为它不是叶子节点路径）

2. 只有当一个节点没有左右子树时，它才是叶子节点

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

迭代法

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> q;if(root == nullptr) return 0;q.push(root);int dep = 1;while(!q.empty()){int size = q.size();for(int i = 0; i < size; i++){TreeNode* cur = q.front();q.pop();if(!cur->left  && !cur->right) return dep;if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}dep++;}return dep;}
};

DFS前序遍历 + 传递当前深度

class Solution {
private:int mindp = INT_MAX;void traverse(TreeNode* cur, int level){if(cur == nullptr) return;if(!cur->left && !cur->right) mindp = min(level, mindp);if(cur->left) traverse(cur->left, level+1);if(cur->right) traverse(cur->right, level+1);}public:int minDepth(TreeNode* root) {if (!root) return 0; traverse(root, 1);return mindp;}
};

 递归解法（DFS）

int minDepth(TreeNode* root) {if (!root) return 0;          // 情况1：空节点if (!root->left)              // 情况2：只有右子树return minDepth(root->right) + 1;if (!root->right)             // 情况3：只有左子树return minDepth(root->left) + 1;return min(minDepth(root->left), minDepth(root->right)) + 1; // 情况4：左右子树都有
}