requirements

Given a binary tree, find its minimum depth.

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

Note: Leaf nodes are nodes that have no child nodes.

Example 1:

Input: root = [3,9,20,null,null,15,7] output: 2Copy the code

Example 2:

Input: root = [2, null, 3, null, 4, null, 5, null, 6] output: 5Copy the code

Code,

class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minDepth(self, root: TreeNode) - >int:
        if root:
            if root.left and root.right:
                return 1 + min(self.minDepth(root.left),self.minDepth(root.right))
            elif root.left:
                return 1 + self.minDepth(root.left)
            elif root.right:
                return 1 + self.minDepth(root.right)
            else:
                return 1 

        else:
            return 0
Copy the code

Another way of thinking

  • More like depth traversal, in traversal, the depth of the root node is continuously added to a list, and finally output the minimum value of the list, which is the minimum depth
class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def minDepth(self, root: TreeNode) - >int:
        if not root:
            return 0

        self.depth_list = list()
        self.findAllDepth(root,0)
        return min(self.depth_list)
    
    def findAllDepth(self,root,depth) :
        if not root.left and not root.right:
            depth += 1
            self.depth_list.append(depth)
            return
        
        if root.left:
            self.findAllDepth(root.left,depth + 1)
        
        if root.right:
            self.findAllDepth(root.right,depth + 1)
        return 
Copy the code

Their thinking: we use recursive way will our minimum depth into the form of expression, when nodes are around us to take the lowest value of two, when only left nodes or only right node, we directly by the depth node, all have no, is 1, the depth of the layer directly returns