leetcode with python:111. Minimum Depth of Binary Tree

题目:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

给定一个binary tree,求root到leaf的最短路径

这题有点104.变体感

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def minDepth(self, root: Optional[TreeNode]) -> int:        if not root:            return 0        if root.left and root.right:            return min(self.minDepth(root.left),self.minDepth(root.right))+1        else:            if root.left:                return self.minDepth(root.left)+1            elif root.right:                return self.minDepth(root.right)+1            else:                return 1

不过这次遇到leaf就要回传1(leaf自己也算一层)往上加了
因为我们这次是左右子树比小
假如一侧是None回传0会导致判断失误(因为那里其实没节点,但取min会取到0)
最后得到的值就是root到leaf的最短路径了
最后执行时间537ms(faster than 94.44%)

那我们下题见