Leecode刷题之旅-C语言/python-111二叉树的最小深度

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

/*

 * @lc app=leetcode.cn id=111 lang=c

 *

 * [111] 二叉树的最小深度

 *

 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/

 *

 * algorithms

 * Easy (37.27%)

 * Total Accepted:    12.2K

 * Total Submissions: 32.6K

 * Testcase Example:  '[3,9,20,null,null,15,7]'

 *

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

 *

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

 *

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

 *

 * 示例:

 *

 * 给定二叉树 [3,9,20,null,null,15,7],

 *

 * ⁠   3

 * ⁠  / \

 * ⁠ 9  20

 * ⁠   /  \

 * ⁠  15   7

 *

 * 返回它的最小深度  2.

 *

 */

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

int min(a,b);

int minDepth(struct TreeNode* root) {

        if (root == NULL) return ;

        if (root->left == NULL && root->right == NULL) return ;

        if (root->left == NULL) return minDepth(root->right) + ;

        else if (root->right == NULL) return minDepth(root->left) + ;

        else return  + min(minDepth(root->left), minDepth(root->right));

}

int min(a,b){

    return a<b?a:b;

}

最小深度和最大深度类似，但是要注意的就是，当左子树为空的时候，只查右子树就可以，右子树为空的时候，只查左子树即可。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

python：

#

# @lc app=leetcode.cn id=111 lang=python3

#

# [111] 二叉树的最小深度

#

# https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/

#

# algorithms

# Easy (37.27%)

# Total Accepted:    12.2K

# Total Submissions: 32.6K

# Testcase Example:  '[3,9,20,null,null,15,7]'

#

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

#

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

#

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

#

# 示例:

#

# 给定二叉树 [3,9,20,null,null,15,7],

#

# ⁠   3

# ⁠  / \

# ⁠ 9  20

# ⁠   /  \

# ⁠  15   7

#

# 返回它的最小深度  2.

#

#

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def minDepth(self, root):

        if root == None:

            return 0

        elif root.left == None and root.right == None:

            return 1

        elif root.left == None and root.right != None:

            return self.minDepth(root.right)+1

        elif root.right ==None and root.left != None:

            return self.minDepth(root.left)+1

        elif root.left != None and root.right !=None:

            return min(self.minDepth(root.left), self.minDepth(root.right))+1