当前位置： 首页 > article >正文

python算法和数据结构刷题[6]：二叉树、堆、BFS\DFS

article 2025/2/3 15:18:17

遍历二叉树

  • 前序遍历NLR：先访问根结点，再前序遍历左子树，最后前序遍历右子树。
  • 中序遍历LNR：先中序遍历左子树，再访问根结点，最后中序遍历右子树。
  • 后序遍历 LRN：先后序遍历左子树，再后序遍历右子树，最后访问根结点。
  • 层次遍历：自上而下、从左到右依次访问每层的结点。

前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

NLR

递归

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []  # 用于存储遍历的结果

        def helper(node):
            # 如果当前节点为空，直接返回
            if not node:
                return
            # 访问根节点
            res.append(node.val)
            # 递归遍历左子树
            helper(node.left)
            # 递归遍历右子树
            helper(node.right)

        # 从根节点开始递归遍历
        helper(root)
        return res

# 示例使用：
# 构建一个简单的二叉树
#     1
#    / \
#   2   3
#  / \
# 4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 创建Solution对象并调用preorderTraversal方法
sol = Solution()
print(sol.preorderTraversal(root))  # 输出应为 [1, 2, 4, 5, 3]

后续遍历

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

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def helper(root):
            if not root:
                return 
            helper(root.left)
            helper(root.right)
            res.append(root.val)
        helper(root)
        return res

中序遍历

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

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def helper(root):
            if not root:
                return 
            helper(root.left)
            res.append(root.val)
            helper(root.right)
        helper(root)
        return res

层次遍历

是一种非常典型的广度优先搜索。

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

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        res,cur_level = [],[root]
        while cur_level:
            temp = []
            next_level = []
            for i in cur_level:
                temp.append(i.val)

                if i.left:
                    next_level.append(i.left)
                if i.right:
                    next_level.append(i.right)
            res.append(temp)
            cur_level = next_level
        return res

重建二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

前序遍历的第一个元素为根节点，而在中序遍历中，该根节点所在位置的左侧为左子树，右侧为右子树。

我们可以根据中序数组的中间位置 1，来确定前序数组的左右部分，由于前序数组第一个是根节点，
所以其左边部分是：[1:mid_index]，右半部分是 [mid_index+1:]

# 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 buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        # 前序遍历第一个值为根节点
        root = TreeNode(preorder[0])
        # 因为没有重复元素，所以可以直接根据值来查找根节点在中序遍历中的位置
        mid = inorder.index(preorder[0])
        # 构建左子树
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        # 构建右子树
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        
        return root

视图

199. 二叉树的右视图 - 力扣（LeetCode）

树中根结点的层次为 0，其他结点的层次是父结点的层次加 1

树的深度是指树中所有结点的层次数的最大值加 1

递归

先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            if depth == len(ans):  # 这个深度首次遇到
                ans.append(node.val)
            dfs(node.right, depth + 1)  # 先递归右子树，保证首次遇到的一定是最右边的节点
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans

时间复杂度：O(n)，其中 n 是二叉树的节点个数。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

二叉搜索树

二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树：
　　    1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　    2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　    3）任意节点的左、右子树也分别为二叉查找树。

　　二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

复杂度分析 

它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。

构建二叉搜索树：依次插入就可以

 如果删除的是只有左子树或者右子树的节点，先找到节点的位置，让这个子树替代这个节点然后删除这个子树的节点

 如果删除的节点有左右子树，找到这个节点的左子树中最大的节点，代替这个节点，然后删除这个最大的节点，或者找右子树中最小的去替代这个节点去代替他。





108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 把 nums[left:right] 转成平衡二叉搜索树
        def dfs(left: int, right: int) -> Optional[TreeNode]:
            if left == right:
                return None
            m = (left + right) // 2
            return TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
        return dfs(0, len(nums))

109. 有序链表转换二叉搜索树 - 力扣（LeetCodF

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        elif not head.next:
            return TreeNode(head.val)
        
        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        root = TreeNode(slow.val)
        pre.next = None

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

二叉搜索树（BST）的中序遍历是有序的

# 定义二叉树节点的类
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        # 初始化节点，val是节点的值，left和right分别指向左子节点和右子节点
        self.val = val
        self.left = left
        self.right = right

# 定义解决第k小元素问题的类
class Solution(object):
    def kthSmallest(self, root, k):
        # 初始化结果变量res和计数器k
        self.res = None
        self.k = k
        # 调用深度优先搜索函数dfs
        self.dfs(root)
        # 返回找到的第k小的值
        return self.res
    
    def dfs(self, node):
        # 如果节点为空或者计数器k已经为0，直接返回
        if not node or self.k == 0:
            return
        # 递归地遍历左子树
        self.dfs(node.left)
        # 遍历完左子树后，计数器减1
        self.k -= 1
        # 如果计数器为0，说明找到了第k小的元素
        if self.k == 0:
            # 将当前节点的值赋给res
            self.res = node.val
            # 并返回，结束递归
            return
        # 如果计数器不为0，继续递归遍历右子树
        self.dfs(node.right)

# 示例使用：
# 构建一个二叉搜索树
#     3
#    / \
#   1   4
#    \
#     2
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)

# 实例化 Solution 类
sol = Solution()
# 调用 kthSmallest 方法寻找第1小的元素
print(sol.kthSmallest(root, 1))  # 输出应该是 1，因为第1小的元素是1

98. 验证二叉搜索树 - 力扣（LeetCode）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helper(root, float('-inf'), float('inf'))
    
    def helper(self, node, min_val, max_val):
        # 如果节点为空，说明已经越过叶子节点，返回True
        if not node:
            return True
        # 如果当前节点的值不在(min_val, max_val)范围内，则不是有效的BST
        if not (min_val < node.val < max_val):
            return False
        # 递归检查左子树和右子树
        # 左子树的最大值是当前节点的值，右子树的最小值是当前节点的值
        return (self.helper(node.left, min_val, node.val) and
                self.helper(node.right, node.val, max_val))

# 示例使用：
# 构建一个二叉树
#     2
#    / \
#   1   3
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

# 实例化 Solution 类并调用 isValidBST 方法
sol = Solution()
print(sol.isValidBST(root))  # 输出应该是 True，因为这是一个有效的BST

求深度

104. 二叉树的最大深度 - 力扣（LeetCode）

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）。

常见 DFS ： 先序遍历、中序遍历、后序遍历。
常见 BFS ： 层序遍历（即按层遍历）。

求树的深度需要遍历树的所有节点，基于 后序遍历（DFS） 和 层序遍历（BFS） 的两种解法。

后序遍历（DFS）

树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1 。


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

 层序遍历（BFS）

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res

110. 平衡二叉树 - 力扣（LeetCode）

判断是否为平衡二叉树

平衡二叉树（AVL树）
1.使树在结构上左右分支平衡，所有节点的（左子树高度-右子树高度）的绝对值<=1。

2.平衡因子=左子树高度-右子树高度，所有节点的平衡因子的绝对值都小于等于1就是平衡二叉树。

3.也是二叉搜索树，只是操作后需要检查是否失衡，发现失衡后需要进行调整。

后序遍历+剪枝

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def recur(root):
            if not root: return 0
            left = recur(root.left)
            if left == -1: return -1
            right = recur(root.right)
            if right == -1: return -1
            return max(left, right) + 1 if abs(left - right) <= 1 else -1

        return recur(root) != -1

求直径

543. 二叉树的直径 - 力扣（LeetCode）

  1. 对于树中的每个节点，计算其左子树和右子树的最大深度。
  2. 节点的直径可以通过左子树深度加上右子树深度再加1（当前节点）来计算。
  3. 更新一个全局变量，记录下所有节点直径的最大值。
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

class Solution:
    def diameterOfBinaryTree(self, root):
        self.max_diameter = 0
        
        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            # 更新全局直径
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            # 返回当前节点的深度
            return max(left_depth, right_depth) + 1
        
        depth(root)
        return self.max_diameter

# 示例使用：
# 构建一个简单的二叉树
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

solution = Solution()
print(solution.diameterOfBinaryTree(root))  # 应该输出3，路径为4 -> 2 -> 1 -> 3

对称

101. 对称二叉树 - 力扣（LeetCode）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSymmetric(root):
    def isMirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val) and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)
    
    return isMirror(root, root)

# 时间复杂度分析：
# 假设树有n个节点，那么每个节点都会被访问一次，所以时间复杂度是O(n)。

# 示例使用：
# 构建一个对称的二叉树
#       1
#      / \
#     2   2
#    / \ / \
#   3  4 4  3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

print(isSymmetric(root))  # 应该输出True，因为树是对称的
  • 时间复杂度：O(n)，其中n是树中节点的数量。每个节点最多被访问两次，一次是在isMirror函数的左边，一次是在右边。
  • 空间复杂度：O(h)，其中h是树的高度。这是由于递归调用的栈空间，最坏情况下树是线性的，空间复杂度为O(n)，平均情况下是O(log n)。

翻转

226. 翻转二叉树 - 力扣（LeetCode）

BFS

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    if root is None:
        return None
    
    # 交换左右子树
    root.left, root.right = root.right, root.left
    
    # 递归反转左右子树
    invertTree(root.left)
    invertTree(root.right)
    
    return root

# 时间复杂度分析：
# 假设树有n个节点，那么每个节点都会被访问一次，所以时间复杂度是O(n)。

# 空间复杂度分析：
# 空间复杂度是O(h)，其中h是树的高度。这是由于递归调用的栈空间，
# 在最坏情况下（树完全倾斜），空间复杂度为O(n)，在平均情况下（树比较平衡）为O(log n)。

# 示例使用：
# 构建一个简单的二叉树
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 反转二叉树
new_root = invertTree(root)

最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

DFS、递归

class TreeNode:
    def __init__(self, x):
        self.val = x  # 节点的值
        self.left = None  # 左子节点
        self.right = None  # 右子节点

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        在二叉树中找到节点p和节点q的最低公共祖先。
        
        :param root: 二叉树的根节点
        :param p: 二叉树中的第一个节点
        :param q: 二叉树中的第二个节点
        :return: 节点p和节点q的最低公共祖先
        """
        
        def dfs(node):
            # 如果当前节点为空，或者当前节点是p或q中的一个，直接返回当前节点
            if not node or node == p or node == q:
                return node
            
            # 递归搜索左子树，寻找p或q
            left = dfs(node.left)
            # 递归搜索右子树，寻找p或q
            right = dfs(node.right)
            
            # 如果左子树和右子树都找到了p或q，说明当前节点是它们的最低公共祖先
            if left and right:
                return node
            # 如果只有左子树找到了p或q，返回左子树的查找结果
            # 否则返回右子树的查找结果
            return left if left else right
        
        # 从根节点开始深度优先搜索
        return dfs(root)

# 使用示例：
# 构建二叉树
#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

# 创建Solution对象
solution = Solution()

# 找到节点5和节点1的最低公共祖先
lca = solution.lowestCommonAncestor(root, root.left, root.right)
print(lca.val)  # 应该输出3，因为节点3是节点5和节点1的最低公共祖先

路径

112. 路径总和 - 力扣（LeetCode）

给定 二叉树 和 targetSum，如果树具有根到叶路径，则返回，使得沿路径的所有值相加等于 targetSum。

DFS：一直向下找到 叶子节点，如果到 叶子节点 时 sum == 0

# 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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root: return False
        if not root.left and not root.right:
            return sum == root.val
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

 BFS 使用 队列 保存遍历到每个节点时的路径和，如果该节点恰好是叶子节点，并且 路径和 正好等于 sum，说明找到了解。

from collections import deque
from typing import Optional

# 定义二叉树节点的类
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], sum: int) -> bool:
        # 如果根节点为空，直接返回False
        if not root:
            return False
        
        # 初始化队列，用于广度优先搜索
        que = deque()
        # 将根节点及其值加入队列
        que.append((root, root.val))
        
        # 开始广度优先搜索
        while que:
            # 从队列中取出节点和当前路径和
            node, path = que.popleft()
            
            # 检查当前节点是否为叶子节点且路径和等于目标和
            if not node.left and not node.right and path == sum:
                return True
            
            # 如果有左子节点，将左子节点及其路径和加入队列
            if node.left:
                que.append((node.left, path + node.left.val))
            
            # 如果有右子节点，将右子节点及其路径和加入队列
            if node.right:
                que.append((node.right, path + node.right.val))
        
        # 如果遍历完所有节点都没有找到符合条件的路径，返回False
        return False

栈：

# 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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        stack = []
        stack.append((root, root.val))
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right and path == sum:
                return True
            if node.left:
                stack.append((node.left, path + node.left.val))
            if node.right:
                stack.append((node.right, path + node.right.val))
        return False

124. 二叉树中的最大路径和 - 力扣（LeetCode）

两个数的和：和自己父节点的和。3个数的和，和自己父节点的和再加上父节点的父节点或者兄弟的和。这样递归。这是一个深度优先搜索问题。一直到根节点结束计算。

lass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')  # 初始化最大路径和为负无穷
        
        def dfs(node, current_sum):
            if not node:
                return 0
            
            # 当前路径和加上当前节点值
            current_sum += node.val
            
            # 更新全局最大路径和
            self.max_sum = max(self.max_sum, current_sum)
            
            # 递归计算左子树和右子树的最大路径和
            left_sum = dfs(node.left, current_sum)
            right_sum = dfs(node.right, current_sum)
            
            # 返回当前节点的最大路径和，选择左子树或右子树中的较大者
            return max(left_sum, right_sum)
        
        # 从根节点开始递归
        dfs(root, 0)
        
        return self.max_sum

# 构建一个简单的二叉树进行测试
#       10
#      /  \
#     2   10
#    / \    \
#   20  1   -25
#            /  \
#           3    4
root = TreeNode(10)
root.left = TreeNode(2, TreeNode(20), TreeNode(1))
root.right = TreeNode(10, None, TreeNode(-25, TreeNode(3), TreeNode(4)))

solution = Solution()
print(solution.maxPathSum(root))  # 应该输出 42 (20 + 2 + 10 + 10)

深度优先搜索DFS

沿着一个分支遍历，直到这个分支的末端，然后回溯并探索另一个分支

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def dfs(node):
    if node is None:
        return
    print(node.val)  # 处理当前节点
    dfs(node.left)   # 递归遍历左子树
    dfs(node.right)  # 递归遍历右子树

# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs(root)  # 输出: 1 2 4 5 3

 200. 岛屿数量 - 力扣（LeetCode）

"岛屿"是指由水平或垂直相邻的1组成的区域，其中"相邻"意味着上下左右四个方向。

 DFS

def num_islands_dfs(grid):
    if not grid:
        return 0

    def dfs(grid, i, j):
        # 检查边界条件和是否为水域
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return
        # 标记当前陆地为已访问（水域）
        grid[i][j] = '0'
        # 递归访问上下左右四个方向
        dfs(grid, i-1, j)
        dfs(grid, i+1, j)
        dfs(grid, i, j-1)
        dfs(grid, i, j+1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            # 如果遇到陆地，则进行深度优先搜索，并增加岛屿计数
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1
    return count

# 示例网格
grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]

print("Number of islands (DFS):", num_islands_dfs(grid))

BFS

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0

    def bfs(grid, i, j):
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            # 检查边界条件和是否为水域
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
                # 标记当前陆地为已访问（水域）
                grid[x][y] = '0'
                # 将上下左右四个方向的陆地加入队列
                queue.extend([(x-1, y), (x+1, y), (x, y-1), (x, y+1)])

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            # 如果遇到陆地，则进行广度优先搜索，并增加岛屿计数
            if grid[i][j] == '1':
                bfs(grid, i, j)
                count += 1
    return count

# 示例网格
grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]

print("Number of islands (BFS):", num_islands_bfs(grid))

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

 


class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0
        def dfs(node, num):
            nonlocal res
            if not node.left and not node.right:
                res += num
                return
            if node.left:
                dfs(node.left, num * 10 + node.left.val)
            if node.right:
                dfs(node.right, num * 10 + node.right.val)
        
        res = 0
        dfs(root, root.val)
        return res

BFS

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = collections.deque([(root, root.val)])
        res = 0
        while queue:
            node, num = queue.popleft()
            if not node.left and not node.right:
                res += num
            if node.left:
                queue.append((node.left, num * 10 + node.left.val))
            if node.right:
                queue.append((node.right, num * 10 + node.right.val))
        return res

广度优先搜索BFS

按照层次顺序访问树或图的节点，首先访问最近的节点，然后逐渐向外扩展。

from collections import deque

def bfs(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()  # 从队列中取出一个节点
        print(node.val)         # 处理当前节点
        if node.left:
            queue.append(node.left)  # 将左子节点加入队列
        if node.right:
            queue.append(node.right) # 将右子节点加入队列

# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

bfs(root)  # 输出: 1 2 3 4 5

 958. 二叉树的完全性检验 - 力扣（LeetCode）

在完全二叉树中，除了最后一个级之外，每个级都被完全填充，并且最后一个级别中的所有节点都尽可能靠左。

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def isCompleteTree(root):
    if not root:
        return True
    
    queue = deque([root])
    end = False  # 标记是否遇到一个节点没有右孩子
    
    while queue:
        node = queue.popleft()
        
        # 如果遇到一个节点没有左孩子但有右孩子，返回False
        if not node.left and node.right:
            return False
        
        # 如果遇到一个节点没有右孩子，标记end为True
        if not node.right:
            end = True
        
        # 如果end为True，则后续的所有节点都必须是叶子节点
        if end and (node.left or node.right):
            return False
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return True

# 示例使用
# 构建一棵树进行测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)

# 检验是否是完全二叉树
print(isCompleteTree(root))  # 应该输出True或False

 695. 岛屿的最大面积 - 力扣（LeetCode）

from collections import deque

def maxAreaOfIsland(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    max_area = 0

    # 定义四个方向的移动
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def bfs(r, c):
        area = 1
        queue = deque([(r, c)])
        visited[r][c] = True

        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and grid[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    area += 1
        return area

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1 and not visited[i][j]:
                max_area = max(max_area, bfs(i, j))

    return max_area

# 示例使用
grid = [
    [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
]

print(maxAreaOfIsland(grid))  # 输出应为最大的岛屿面积

堆

根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆，堆总是一棵完全二叉树。

在优先队列中，元素按照优先级的高低排列，而不是按照它们进入队列的顺序。

215. 数组中的第K个最大元素 - 力扣（LeetCode）

堆排序

维护一个大小为k的最小堆，堆顶是这k个数里的最小的，遍历完数组后返回堆顶元素即可

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]


http://www.kler.cn/a/529909.html

相关文章：

  • 前端 | 深入理解Promise
  • 使用MATLAB进行雷达数据采集可视化
  • 玩转Docker | 使用Docker部署MySQL数据库
  • 十分钟快速上手 markdown
  • Docker 部署 GLPI（IT 资产管理软件系统）
  • H264原始码流格式分析
  • 机器学习算法在网络安全中的实践
  • 系统学习算法： 专题八 二叉树中的深搜
  • Node.js——异步编程(异步：阻塞与非阻塞、JavaScript执行机制、callBack hell 回调地狱，Promise、Async await)
  • Stable Diffusion创始人：DeepSeek没有抄袭！
  • 深入浅出并查集（不相交集合实现思路）
  • 2025年02月02日Github流行趋势
  • 【最长不下降子序列——树状数组、线段树、LIS】
  • 图像分割任务的数据预处理
  • 012-51单片机CLD1602显示万年历+闹钟+农历+整点报时
  • XML DOM 浏览器差异
  • 【AI】人工智能没那么神秘！
  • 基于WiFi的智能照明控制系统的设计与实现（论文+源码）
  • 46【什么是原生开发】
  • Vue3 表单：全面解析与最佳实践
  • C++基础学习
  • Baklib构建高效协同的基于云的内容中台解决方案
  • 《苍穹外卖》项目学习记录-Day11订单统计
  • React中useState()钩子和函数式组件底层渲染流程详解
  • 【Linux系统】进程间通信：浅谈 SystemV 标准的消息队列和信号量
  • Python - pyautogui库 模拟鼠标和键盘执行GUI任务