111. 二叉树的最小深度

2018-10-30  本文已影响24人  小王同学加油

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

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

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


image.png

分析

第一版本:

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;
}
上一篇 下一篇

猜你喜欢

热点阅读