【Leetcode】111. Minimum Depth of Binary Tree 解题报告

求树的最小深度，深度为根节点到叶子节点的长度

方法1 递归

对于某个非None节点我们返回其左右子树最小的深度，但是要注意返回的值是否为0，如果为0，其最小深度就是另外一个子树的深度

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        else:
            l = self.minDepth(root.left)
            r = self.minDepth(root.right)
            return l + r + 1 if (l==0 or r ==0) else min(l, r) +1

方法2 递归+全局变量

递归，当递归到叶子节点时，将其深度与最终结果比较

class Solution2:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        self.res = float("inf")
        self.DFS(root, 1)
        return self.res

    def DFS(self, root, level):
        if root.left == None and root.right == None:
            self.res = min(level, self.res)
        else:
            if root.left:
                self.DFS(root.left, level+1)
            if root.right:
                self.DFS(root.right, level+1)

方法3 非递归深搜

class Solution3:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        res = float("inf")
        stack = [[root,1]]
        while(len(stack)):
            node,depth = stack.pop()
            if node.left == None and node.right == None:
                res = min(res, depth)
            else:
                if node.left:
                    stack.extend([[node.left, depth+1]])
                if node.right:
                    stack.extend([[node.right, depth+1]])
        return res

方法四 非递归广搜

class Solution4:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        depth =0
        from collections import deque
        queue = deque()
        queue.append(root)
        while(len(queue)):
            depth +=1
            length = len(queue)
            for i in range(length):
                node =queue.popleft()
                if node.left == None and node.right == None:
                    return depth
                else:
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
        return depth