[LeetCode] Minimum Depth of Binary Tree 파이썬 (recursion)

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

class Solution:
    # @param root, a tree node
    # @return an integer
    def minDepth(self, root):
        if root is None:
            return 0

        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

max와 다른 점은 leaf node 까지의 min depth 라는 조건인데

 

그렇기 때문에 if root.left and root.right: 즉, leaf node가 아닌 parent 노드(root)에서 양쪽의 children이 다 있다면 최단 거리를 return

만약에 한쪽에만 children node가 있다면 max탐색을 해줘야 한다.

 

출처: github.com/jiapengwen/LeetCode/blob/master/Python/minimum-depth-of-binary-tree.py