111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

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

说明: 叶子节点是指没有子节点的节点。

image.png

分析

• 最大的深度理解，最小深度一下子懵了不知道如何解析
• 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
  这个问题难点在哪来 加入是null节点的距离就不能需要计算

第一版本：

int minDepth(struct TreeNode* root) {
  if (root ==NULL) 
  {
         return 0;
  }
    
    int left=minDepth(root->left);
    int right=minDepth(root->right);
    //1 节点本身  2 left right子节点
    return left<right?left:right+1;
}

image.png

运算符优先级 （left<right?left:right）+1;

第二版本：

int minDepth(struct TreeNode* root) {
  if (root ==NULL) 
  {
         return 0;
  }
    
    int left=minDepth(root->left);
    int right=minDepth(root->right);
    //1 节点本身  2 left right子节点
    return （left<right?left:right）+1;
}

image.png

min(0,any)=0 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

第三版本：

int minDepth(struct TreeNode* root) {
  if (root ==NULL) 
  {
         return 0;
  }
    
    int left=minDepth(root->left);
    int right=minDepth(root->right);
    if (left ==0 || right ==0) 
    {
       return left+right+1;    //最坏情况是没有最大深度就是最小深度 因为只有一个深度 一个路径
    }
    //1 节点本身  2 left right子节点
    return （left<right?left:right）+1;
}