给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

  1. 3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7
  6. 返回它的最小深度  2.

c plus

  • 递归
    和最大深度不同的是要考虑左右子树一个为空一个不为空的情况，这种情况时，为空的子树的深度不可算在内
    题解
    1. class Solution {
    2. public:
    3.   int minDepth(TreeNode* root) {
    4.       if (!root)  return 0;
    5.       int left = minDepth(root->left);
    6.       int right = minDepth(root->right);
    7.       return (!root->left || !root->right) ? left + right + 1 : min(left, right) + 1;////如果有一个空，则+1,否则最小值+1
    8.   }
    9. };

%0A%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E6%89%BE%E5%87%BA%E5%85%B6%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6%E3%80%82%0A%0A%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6%E6%98%AF%E4%BB%8E%E6%A0%B9%E8%8A%82%E7%82%B9%E5%88%B0%E6%9C%80%E8%BF%91%E5%8F%B6%E5%AD%90%E8%8A%82%E7%82%B9%E7%9A%84%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E4%B8%8A%E7%9A%84%E8%8A%82%E7%82%B9%E6%95%B0%E9%87%8F%E3%80%82%0A%0A%E8%AF%B4%E6%98%8E%3A%20%E5%8F%B6%E5%AD%90%E8%8A%82%E7%82%B9%E6%98%AF%E6%8C%87%E6%B2%A1%E6%9C%89%E5%AD%90%E8%8A%82%E7%82%B9%E7%9A%84%E8%8A%82%E7%82%B9%E3%80%82%0A%60%60%60%0A%20%20%20%203%0A%20%20%20%2F%20%5C%0A%20%209%20%2020%0A%20%20%20%20%2F%20%20%5C%0A%20%20%2015%20%20%207%0A%E8%BF%94%E5%9B%9E%E5%AE%83%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6%20%202.%0A%60%60%60%0A%0A%23%23%23%20c%20plus%0A%0A%0A%20%E9%80%92%E5%BD%92%0A%20%20%E5%92%8C%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6%E4%B8%8D%E5%90%8C%E7%9A%84%E6%98%AF%E8%A6%81%E8%80%83%E8%99%91%E5%B7%A6%E5%8F%B3%E5%AD%90%E6%A0%91%E4%B8%80%E4%B8%AA%E4%B8%BA%E7%A9%BA%E4%B8%80%E4%B8%AA%E4%B8%8D%E4%B8%BA%E7%A9%BA%E7%9A%84%E6%83%85%E5%86%B5%EF%BC%8C%E8%BF%99%E7%A7%8D%E6%83%85%E5%86%B5%E6%97%B6%EF%BC%8C%E4%B8%BA%E7%A9%BA%E7%9A%84%E5%AD%90%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6%E4%B8%8D%E5%8F%AF%E7%AE%97%E5%9C%A8%E5%86%85%0A%20%20%20%20%0A%20%20%20%20%5B%E9%A2%98%E8%A7%A3%5D(https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fminimum-depth-of-binary-tree%2Fsolution%2Fjava-di-gui-he-fei-di-gui-liang-chong-fang-shi-de-%2F)%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20int%20minDepth(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20if%20(!root)%20%20return%200%3B%0A%20%20%20%20%20%20%20%20int%20left%20%3D%20minDepth(root-%3Eleft)%3B%0A%20%20%20%20%20%20%20%20int%20right%20%3D%20minDepth(root-%3Eright)%3B%0A%20%20%20%20%20%20%20%20return%20(!root-%3Eleft%20%7C%7C%20!root-%3Eright)%20%3F%20left%20%2B%20right%20%2B%201%20%3A%20min(left%2C%20right)%20%2B%201%3B%2F%2F%2F%2F%E5%A6%82%E6%9E%9C%E6%9C%89%E4%B8%80%E4%B8%AA%E7%A9%BA%EF%BC%8C%E5%88%99%2B1%2C%E5%90%A6%E5%88%99%E6%9C%80%E5%B0%8F%E5%80%BC%2B1%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A%0A%0A