[leetcode] 111. Minimum Depth of Binary Tree

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

 

 

leaf node 까지의 depth 중 가장 짧은 depth 를 찾는다.

직관적으로 이해하기 쉬운 재귀 함수를 사용하여 구현 가능하다.

주어진 tree 가 None 이거나, 주어진 tree가 leaf node 일 때 (자식이 전혀 없을 때) 재귀 함수가 끝난다.

tree 의 left 혹은 right 가 존재하면, 재귀 함수를 호출한다.

재귀 함수가 반환한 값에 1을 더한 값 중 작은 것을 선택하여 반환한다.

 

 

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if(not root): return 0
        if(not root.left and not root.right): return 1
        if(root.left and not root.right): return self.minDepth(root.left) + 1
        if(root.right and not root.left): return self.minDepth(root.right) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

 

 

 

 

재귀 함수를 사용하지 않고, queue 를 이용할 수 있다.

Tree 의 level 을 측정하는 방식이다.

Tree 를 순회하면서 가장 먼저 만나는 leaf node 가 갖는 level 이 최소 깊이이다.

queue 에서 pop 이 처리되는 동안 append 가 발생하기 때문에, 무한히 pop & append 가 반복될 수 있다.

따라서 얼만큼 pop 을 할 지 정해주어야 한다.

 

 

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if(not root): return 0
        level=1
        dq = deque([root])
        while(dq):
            for i in range(0,len(dq)):
                tree = dq.popleft()
                if(not tree.left and not tree.right): return level
                if(tree.left): dq.append(tree.left)
                if(tree.right): dq.append(tree.right)
            level+=1
        return level

 

 

 

 

 

 

 

---

 

 

 

< English (feedback by ChatGPT) >

 

The task is to find the minimum depth among any depths to leaf node.

(The task is to find the minimum depth among all paths to a leaf node.)

 

We can implement codes using a recursive function which is intuitive.

(We can implement this using a recursive function, which is intuitive.)

 

When the given tree is None or the given tree is a leaf node(without any children), then the recursive functions ends.

(The recursive function ends when the given tree is None or when the node is a leaf (i.e. it has no children).)

 

We call the recursive function when the tree has a left child or a right child.

(If the node has a left or right child, we call the recursive function on them.)

 

Also it returns a minimum value between 1 + a number which the recursive function returns.

(We return the smaller value between the results of the recursive calls, adding 1 to account for the current level.)

 

It's possible to implement using queue, instead of a recursive function.

(Alternatively, we can use a queue instead of recursion.)

 

It's a way to calculate Tree level.

(This approach measures the tree’s level (Breadth-First Search).)

 

While iterating the tree, the level of the leaf node we meet first is the minimum depth.

(As we traverse the tree level by level, the depth of the first leaf node we encounter is the minimum depth.)

 

While we pop from the queue, append also happens. and it could make a loop to pop and append running forever.

(Since nodes are appended to the queue as we pop them, this could cause an infinite pop-and-append loop.)

 

Thus, we need to set how many times pop from the queue.

(To avoid this, we need to define the number of nodes to pop at each level during traversal.)