Leetcode111.二叉树的最小深度

题目描述：

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：

叶子节点是指没有子节点的节点

示例：

给定二叉树 [3,9,20,null,null,15,7]， 返回它的最小深度2。

image.png

解题思路一：递归

这里要注意两点：

• 叶子节点是指没有子节点的节点
• 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
  例如：二叉树[1,2]，返回的最小深度为2，并非1。（即需要排除None子节点）
  image.png

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        
        if left and right:
            return min(left, right) + 1  # 当双子节点不为None时，返回其最小深度
        else:
            return max(left, right) + 1  # 当其中一个子节点为None时，返回其最大深度

———————————————————————————————————————

以下为官方解答：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode/

解题思路二：深度优先搜索迭代

我们可以利用栈将上述解法中的递归变成迭代。

想法是对于每个节点，按照深度优先搜索的策略访问，同时在访问到叶子节点时更新最小深度。

我们从一个包含根节点的栈开始，当前深度为 1 。
然后开始迭代：弹出当前栈顶元素，将它的孩子节点压入栈中。当遇到叶子节点时更新最小深度。

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        else:
            stack, min_depth = [(1, root),], float('inf')
        
        while stack:
            depth, root = stack.pop()
            children = [root.left, root.right]
            if not any(children):
                min_depth = min(depth, min_depth)
            for c in children:
                if c:
                    stack.append((depth + 1, c))
        
        return min_depth 

复杂度分析

• 时间复杂度：每个节点恰好被访问一遍，复杂度为 O(N)。
• 空间复杂度：最坏情况下我们会在栈中保存整棵树，此时空间复杂度为 O(N)。

解题思路三：宽度优先搜索迭代

深度优先搜索方法的缺陷是所有节点都必须访问到，以保证能够找到最小深度。因此复杂度是 O(N)。

一个优化的方法是利用宽度优先搜索，我们按照树的层次去迭代，第一个访问到的叶子就是最小深度的节点，这样就不要遍历所有的节点了。

from collections import deque
class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        else:
            node_deque = deque([(1, root),])
        
        while node_deque:
            depth, root = node_deque.popleft()
            children = [root.left, root.right]
            if not any(children):
                return depth
            for c in children:
                if c:
                    node_deque.append((depth + 1, c))

复杂度分析

• 时间复杂度：最坏情况下，这是一棵平衡树，我们需要按照树的层次一层一层的访问完所有节点，除去最后一层的节点。这样访问了 N/2 个节点，因此复杂度是 O(N)。
• 空间复杂度：和时间复杂度相同，也是 O(N)。