Leetcode111.二叉树的最小深度

2019-08-02  本文已影响0人  淌水希恩
题目描述:

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

说明:

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

示例:

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

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)。

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

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))
复杂度分析
上一篇 下一篇

猜你喜欢

热点阅读