算法题--求一棵二叉树的深度

image.png

0. 链接

题目链接

1. 题目

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

2. 思路1: 递归

• 分析题意, 到叶子节点的距离才是深度, 而叶子节点是指左右子节点均为None的节点
• 时间复杂度 O(N)
• 空间复杂度 O(logN), 最坏情况 O(N)

3. 代码

# coding:utf8


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


class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root.left is None and root.right is None:
            return 1
        elif root.left is not None and root.right is not None:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
        elif root.left is not None and root.right is None:
            return 1 + self.minDepth(root.left)
        elif root.left is None and root.right is not None:
            return 1 + self.minDepth(root.right)
        else:
            return 1


solution = Solution()

root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.minDepth(root1))

root2 = node = TreeNode(1)
node.left = TreeNode(2)
print(solution.minDepth(root2))

输出结果

2
2

4. 结果

image.png

5. 思路2: 利用队列+分层迭代

• 为了减少递归的时间和空间消耗，改为用队列+分层迭代来实现, 这样遇到非平衡的树，并非需要遍历完所有节点, 即可提前得知结果
• 二叉树的深度，取决于第一个到达叶子节点所在的层，所以分层遍历到遇到叶子节点，即获得了深度
• 时间复杂度 O(N)
• 空间复杂度 O(N)
• 理论的复杂度评级，看不出此法的优越性，因为它可以提前返回结果, 对于非平衡树来说, 比递归法好得多

6. 代码

# coding:utf8


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


class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        queue = list()
        queue.append(root)
        level = 1
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                if node.left is None and node.right is None:
                    return level
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            level += 1

        return level


solution = Solution()

root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.minDepth(root1))

root2 = node = TreeNode(1)
node.left = TreeNode(2)
print(solution.minDepth(root2))

输出结果

2
2

7. 结果

image.png