ARTICLE · 1071659
2026网安习题大全(4)
题目31：二叉树展开为链表
问题描述：给定一个二叉树的根节点 root，将它展开为一个单链表。展开后的单链表应该使用 right 指针连接，且顺序与二叉树的前序遍历相同。
解题思路：使用前驱节点法。对于当前节点，若其有左子树，则找到左子树的最右节点，将当前节点的右子树接到该最右节点之后，然后将左子树移到右边，左子树置空。最后移动到下一个右子节点继续处理。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 def flatten(root): curr = root while curr: if curr.left: prev = curr.left while prev.right: prev = prev.right prev.right = curr.right curr.right = curr.left curr.left = None curr = curr.right
题目32：路径总和
问题描述：给定一个二叉树的根节点 root 和一个目标整数 targetSum，判断该树中是否存在根节点到叶子节点的路径，使得路径上所有节点值之和等于 targetSum。
解题思路：使用递归。从根节点出发，每经过一个节点就将目标值减去该节点值。当到达叶子节点时，判断剩余目标值是否等于 0。
Python 代码示例：
1 2 3 4 5 6 7 8 9 def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return root.val == targetSum return (hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val))
题目33：二叉树中的最近公共祖先
问题描述：给定一个二叉树的根节点 root 和两个节点 p、q，找到这两个节点的最近公共祖先（LCA）。
解题思路：使用递归。若当前节点为空或等于 p 或 q，返回当前节点。递归左右子树，若左右子树均返回非空，则当前节点即为 LCA；否则返回非空的那一侧。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 def lowestCommonAncestor(root, p, q): if not root or root == p or root == q: return root left = lowestCommonAncestor(root.left, p, q) right = lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right
题目34：对称二叉树
问题描述：给定一个二叉树的根节点 root，检查它是否轴对称。
解题思路：使用递归辅助函数 isMirror(left, right)，判断两个子树是否互为镜像：左子树的左孩子与右子树的右孩子镜像，左子树的右孩子与右子树的左孩子镜像。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def isSymmetric(root): if not root: return True def isMirror(left, right): if not left and not right: return True if not left or not right: return False if left.val != right.val: return False return (isMirror(left.left, right.right) and isMirror(left.right, right.left)) return isMirror(root.left, root.right)
题目35：二叉树的右视图
问题描述：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解题思路：使用 BFS 层序遍历。每层最后一个节点即为从右侧能看到的节点，将其加入结果列表。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import dequedef rightSideView(root): if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) for i in range(level_size): node = queue.popleft() if i == level_size - 1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
题目36：搜索旋转排序数组
问题描述：给定一个按升序排列的整数数组 nums，该数组在某个未知位置被旋转过（例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]）。给定目标值 target，如果数组中存在该目标值则返回其索引，否则返回 -1。要求时间复杂度为 O(log n)。
解题思路：使用二分查找。每次取中点后，判断左半部分还是右半部分是有序的，然后根据目标值是否在有序区间内来缩小搜索范围。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 左半部分有序 if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 右半部分有序 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1
题目37：在排序数组中查找元素的第一个和最后一个位置
问题描述：给定一个按照升序排列的整数数组 nums 和一个目标值 target，找出目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。要求时间复杂度为 O(log n)。
解题思路：使用两次二分查找。第一次查找目标值的左边界（第一个等于 target 的位置），第二次查找目标值的右边界（最后一个等于 target 的位置）。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def searchRange(nums, target): def findBound(is_left): left, right = 0, len(nums) - 1 bound = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: bound = mid if is_left: right = mid - 1 else: left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return bound return [findBound(True), findBound(False)]
题目38：寻找旋转排序数组中的最小值
问题描述：给定一个按升序排列的数组 nums，该数组在某个未知位置被旋转过。请找出数组中的最小元素。要求时间复杂度为 O(log n)。
解题思路：使用二分查找。比较中点元素与右边界元素：若中点元素大于右边界元素，说明最小值在右半部分；否则最小值在左半部分（包括中点）。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 def findMin(nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]
题目39：搜索二维矩阵
问题描述：给定一个 m x n 的矩阵 matrix，其每行中的整数从左到右按升序排列，且每行的第一个整数大于前一行的最后一个整数。给定目标值 target，判断该目标值是否存在于矩阵中。
解题思路：将二维矩阵视为一个长度为 m * n 的一维有序数组，使用二分查找。通过 mid // n 和 mid % n 将一维索引映射到二维坐标。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def searchMatrix(matrix, target): if not matrix: return False rows, cols = len(matrix), len(matrix[0]) left, right = 0, rows * cols - 1 while left <= right: mid = (left + right) // 2 val = matrix[mid // cols][mid % cols] if val == target: return True elif val < target: left = mid + 1 else: right = mid - 1 return False
题目40：寻找两个正序数组的中位数
问题描述：给定两个大小分别为 m 和 n 的正序（升序）数组 nums1 和 nums2，找出并返回这两个正序数组的中位数。要求时间复杂度为 O(log(m + n))。
解题思路：使用二分查找划分两个数组。在较短的数组上进行二分，找到一个划分点，使得左半部分元素个数等于右半部分（或相差 1），且左半部分最大值不大于右半部分最小值。根据划分点计算中位数。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def findMedianSortedArrays(nums1, nums2): if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) total_left = (m + n + 1) // 2 left, right = 0, m while left <= right: i = (left + right) // 2 j = total_left - i left_max1 = nums1[i - 1] if i > 0 else float('-inf') right_min1 = nums1[i] if i < m else float('inf') left_max2 = nums2[j - 1] if j > 0 else float('-inf') right_min2 = nums2[j] if j < n else float('inf') if left_max1 <= right_min2 and left_max2 <= right_min1: if (m + n) % 2 == 1: return max(left_max1, left_max2) return (max(left_max1, left_max2) + min(right_min1, right_min2)) / 2 elif left_max1 > right_min2: right = i - 1 else: left = i + 1