美文网首页
[LeetCode] Minimum Depth of Bina

[LeetCode] Minimum Depth of Bina

作者: lyy0905 | 来源:发表于2018-03-08 10:27 被阅读0次

题目

原题地址

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路

最短路径的定义是从root到叶子节点的最少节点数,从root开始递归查找,对于每个节点需要判断子节点的情况:

  • 左子节点为空,右子节点不为空:继续查找右子节点
  • 左子节点不为空,右子节点为空:继续查找左子节点
  • 左右子节点都不为空:分别查找两个子节点并返回两者较小的值
  • 左右子节点都为空:直接返回

上述四种情况可以进一步合并,只要考虑一个子节点为空,另一个子节点不为空的特殊情况:因为空节点返回值为0,所以只要将左右两个子节点的返回值相加就可以了;其他情况只要无脑取两个子节点的较小返回值。

  1
   \
    2
   / 
  3    

因为要找到叶子节点,对于节点2,不能直接取两个子节点的较小值。

python代码

# 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 root == None:
            return 0
        if root.left == None or root.right == None:
            return self.minDepth(root.left) + self.minDepth(root.right) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

相关文章

网友评论

      本文标题:[LeetCode] Minimum Depth of Bina

      本文链接:https://www.haomeiwen.com/subject/pkvefftx.html