你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

LeetCode 题集:深度优先搜索(DFS)、广度优先搜索(BFS)

2021-11-3 18:30:37

本文介绍 LeetCode 题集中,有关深度优先搜索(DFS)和广度优先搜索(BFS)的问题。


110. Balanced Binary Tree(平衡二叉树)


问题描述

LeetCode 110 问题描述 I
LeetCode 110 问题描述 II

思路与代码


本题可采用深度优先搜索的方法,遍历每一个子节点下是否为平衡树,输出最终结果。

代码如下:

# 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 isBalanced(self, root: TreeNode) -> bool:
        def run(root: TreeNode) -> bool:
            def get_depth(root: TreeNode):
                if not root:
                    return 0
                else:
                    return max(get_depth(root.left), get_depth(root.right)) + 1

            if not root:
                return True

            # not balanced
            if abs(get_depth(root.left) - get_depth(root.right)) > 1:
                return False

            return run(root.left) and run(root.right)

        return run(root=root)

运行效果:
LeetCode 110 运行效果 1

效果有些不理想,这里提出一种优化方案。由于只要有一个子节点下为不平衡树,整体即为不平衡树,因此可以在获取深度时即做剪枝。

代码如下:

# 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 isBalanced(self, root: TreeNode) -> bool:
        def run(root: TreeNode) -> bool:  # 返回 -1 即为提前剪枝
            def get_depth(root: TreeNode):
                if not root:
                    return 0
                
                lh = get_depth(root.left)
                if lh == -1:
                    return -1
                rh = get_depth(root.right)
                if rh == -1:
                    return -1

                if abs(lh - rh) > 1:
                    return -1

                return max(lh, rh) + 1

            if not root:
                return True

            return get_depth(root) != -1

        return run(root=root)

运行效果:
LeetCode 110 运行效果 2


111. Minimum Depth of Binary Tree(二叉树的最小深度)


问题描述


LeetCode 111 问题描述 I
LeetCode 111 问题描述 II

思路与代码


关于本题,介绍深度优先搜索和广度优先搜索两种思路。

深度优先搜索(DFS)


深度优先搜索采用递归的方式实现。

代码如下:

# 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:
        def run(root: TreeNode) -> int:
            if not root:
                return 0

            ld = run(root.left)
            rd = run(root.right)

            if not ld:
                return rd + 1
            elif not rd:
                return ld + 1

            return min(ld, rd) + 1

        return run(root=root)

运行结果:
LeetCode 111 运行效果

广度优先搜索(BFS)


广度优先搜索采用队列的数据结构实现,此处采用 Python 语言的 list 数据类型模拟队列的操作。

代码如下:

# 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 not root:
            return 0

        list_queue = []
        list_queue.append(root)
        min_depth = 1
        cur_size = 0
        while list_queue:
            cur_size = len(list_queue)
            
            for i in range(cur_size):
                # pop the head of queue
                node = list_queue[0]
                list_queue = list_queue[1:]

                # no child nodes
                if not node.left and not node.right:
                    return min_depth

                # add child nodes to queue
                if node.left:
                    list_queue.append(node.left)
                if node.right:
                    list_queue.append(node.right)

            min_depth += 1

        return min_depth

运行效果:
LeetCode 111 运行效果 2