0111._minimum_depth_of_binary_search_tree.md

Navigation

• Navigation
• Tags
• Links:
• Solution 1 DFS，递归写法
• Solution 2 DFS迭代写法(Stack)
• Solution 3 BFS
• 总结

Tags

1. 树
2. DFS
3. BFS

Links:

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

Solution 1 DFS，递归写法

class Solution:
    def minDepth(self, root):

        if not root: 
            return 0 
        
        children = [root.left, root.right]
        
        # 证明在叶子节点（left和right都是None）。和0104题的核心区别在这
        if not any(children):
            return 1
        
        min_depth = float('inf')
        for c in children:
            if c:
                min_depth = min(self.minDepth(c), min_depth)
        return min_depth + 1 

---

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        
        elif not root.left and root.right:
            return self.minDepth(root.right) + 1
        
        elif root.left and not root.right:
            return self.minDepth(root.left) + 1
        
        else:   # 证明在叶子节点（left和right都是None）和0104题的核心区别在这
            return 1

Solution 2 DFS迭代写法(Stack)

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        
        stack = [(1, root)]
        min_depth = float('inf')

        while stack:
            depth, root = stack.pop()
            children = [root.left, root.right]
            
            if not any(children):   # 在叶子节点 和0104题的核心区别在这
                min_depth = min(depth, min_depth)
                
            for c in children:
                if c:
                    stack.append((depth + 1, c))
        
        return min_depth 

---

# 不用any的写法1
class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        
        stack = [(1, root)]
        min_depth = float('inf')

        while stack:
            depth, root = stack.pop()
            
            if root:
                if not root.left and not root.right:    # 和0104题的核心区别在这
                    min_depth = min(depth, min_depth)

                stack.append((depth+1, root.left))
                stack.append((depth+1, root.right))


        return min_depth

---

# 不用any的写法2
class Solution:
    def minDepth(self, root):
        if not root:
            return 0
           
        stack = [(1, root)]
        min_depth = float('inf')

        while stack:
            depth, root = stack.pop()
            
        
            if not root.left and not root.right:    # 和0104题的核心区别在这
                min_depth = min(depth, min_depth)

            if root.left:
                stack.append((depth+1, root.left))
                
            if root.right:
                stack.append((depth+1, root.right))

        return min_depth

Solution 3 BFS

第一个访问到的叶子就是最小深度的节点，这样就不要像Solution1和2那样遍历所有的节点了。

from collections import deque
class Solution:
    def minDepth(self, root):
        if not root:
            return 0
    
        node_deque = deque([(1, root),])
        
        while node_deque:
            depth, root = node_deque.popleft()
            children = [root.left, root.right]

            if not any(children):   # 和0104题的核心区别在这
                return depth

            for c in children:
                if c:
                    node_deque.append((depth + 1, c))

---

# 不用any的写法1
from collections import deque
class Solution:
    def minDepth(self, root):
        if not root:
            return 0
    
        node_deque = deque([(1, root),])
        
        while node_deque:
            depth, root = node_deque.popleft()
            
            if root:
                if not root.left and not root.right:    # 和0104题的核心区别在这
                    return depth

                node_deque.append((depth+1, root.left))
                node_deque.append((depth+1, root.right))

---

# 不用any的写法2
from collections import deque
class Solution:
    def minDepth(self, root):
        if not root:
            return 0
    
        node_deque = deque([(1, root),])
        
        while node_deque:
            depth, root = node_deque.popleft()
            
            if not root.left and not root.right:    # 和0104题的核心区别在这
                return depth

            if root.left:
                node_deque.append((depth+1, root.left))
            if root.right:
                node_deque.append((depth+1, root.right))

总结

1. 和0104：“找出二叉树的最大深度”相对。

2. 核心区别在于，寻找最小深度是在节点为叶子节点if not root.left and not root.right才进行操作。也即是，用DFS找到叶子节点，才进行min()操作。用BFS找到第一个叶子节点，才返回当前深度，这个深度就是最小深度。