题目一：从转发数据中求原视频用户以及转发的最长深度
在数据处理和算法面试中，常常会遇到一些基于实际业务场景的题目，
比如根据用户转发数据来分析原视频用户以及转发深度。
今天就来探讨一道这样的面试题：给定被转发用户和转发用户两组数据，求原视频的用户以及转发的最长深度。
有两种数据，分别记录被转发的用户和转发的用户，数据示例如下：
- from：1，1，2，2，3，6
- to：2，3，4，5，6，7
问题分析
- 要求从这两组数据中找出原视频的用户（即没有被其他用户转发，却转发给了其他用户的用户），
- 同时计算出转发的最长深度（从原视频用户开始，到最终转发用户经过的转发次数）。
解题思路
寻找原视频用户
- 原视频用户的特点是在
to列表中没有出现过，但在from列表中出现。 - 我们可以利用 Python 中的集合操作，先将
to列表转换为集合，方便快速判断元素是否存在，然后遍历from列表，筛选出不在to集合中的元素，这些元素就是原视频用户。
计算转发最长深度
为计算转发最长深度，我们可以构建一个图结构，以用户为节点，转发关系为边。
从原视频用户开始进行广度优先搜索（BFS），每经过一层节点，深度就增加1，当遍历完所有可达节点后，记录下最大的深度值，即为转发的最长深度 。
from collections import defaultdict def find_original_and_max_depth(from_users, to_users): # 找出原视频的用户 original_users = set(from_users) - set(to_users) # 构建邻接表来表示树结构 tree = defaultdict(list) for f, t in zip(from_users, to_users): tree[f].append(t) # 计算每个原视频用户的最大深度 max_depth = 0 for user in original_users: # 使用队列进行广度优先搜索来计算深度 queue = [(user, 1)] # (用户, 深度) current_max = 0 while queue: current_user, depth = queue.pop(0) current_max = max(current_max, depth) if current_user in tree: for child in tree[current_user]: queue.append((child, depth + 1)) max_depth = max(max_depth, current_max) return original_users, max_depth # 示例数据 from_users = [1, 1, 2, 2, 3, 6] to_users = [2, 3, 4, 5, 6, 7] # 计算结果 original, depth = find_original_and_max_depth(from_users, to_users) print("原视频的用户:", original) print("转发的最长深度:", depth)
题目二：在一棵二叉排序树中，找到比给定数值小的最大节点
要在二叉排序树（BST）中找到比给定数值小的最大节点，可以通过递归或迭代的方式遍历树结构。以下是详细的解决思路和代码实现：
方法思路
二叉排序树特性：左子树所有节点值 < 根节点值 < 右子树所有节点值。
递归遍历：
如果当前节点值 大于等于 目标值，递归向左子树查找（因为右子树的所有值都更大，不可能是答案）。
如果当前节点值 小于 目标值，递归向右子树查找更大的候选值，同时记录当前节点为候选答案。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def find_largest_smaller(root, target): candidate = None current = root while current: if current.val < target: # 当前节点符合条件，记录为候选，并尝试向右找更大的 candidate = current current = current.right else: # 当前节点值 >= target，向左找更小的值 current = current.left return candidate # 示例用法 # 构建 BST: [5,3,7,2,4,6,8] root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(7) root.left.left = TreeNode(2) root.left.right = TreeNode(4) root.right.left = TreeNode(6) root.right.right = TreeNode(8) # 查找比 6 小的最大节点 result = find_largest_smaller(root, 6) print(result.val if result else "None") # 输出: 5