目录题目思路Code题目业务数据处理中经常使用二叉树来表示数据结构为了存储时尽可能节约空间占用需要找出树中重复的子树。给定定义的一棵二叉树按照要求输出这棵二叉树中所有的重复子树对于同一类重复的子树只需要返回其中一个结果即可。输入一叉树的节点。输出重复子树构成的字符串数组重复子树的序列化规则按照前序遍历输出空节点用 # 表示节点值直接输出用逗号分隔例如叶子结点 2 的序列化为 2,#,#字符串数组的输出顺序为序列化后节点多的子树放到前面如果节点数一样则根据子树前序遍历序列输出。注意没有找到重复子树则输出空数组。补充说明1. 如果两棵树具有相同的结构和相同的结点值则认为二者是重复的2. 输入示例是二叉树的层序遍历空节点用 # 表示。输入描述原始二叉树的层序遍历结构。输入为一行节点之间使用英文逗号分隔。输出描述按照要求输出所有重复子树序列化结构。多个子树之间按照节点数多优先节点数相同的根据子树前序遍历序列输出逐行输出。如果没有找到重复子树则输出空内容。说明补充1. 二叉树节点值按输入原样作为字符串处理# 仅表示空节点。2. 重复子树的判定基于“结构相同且对应节点值相同”。3. 输出时同一种重复子树只输出一次。4. 为了和示例保持一致输出使用前序序列化结果每个结果单独占一行。示例1输入1,2,3,4,#,2,4,#,#,4输出2,4,#,#,#4,#,#说明子树 4,#,# 出现多次。子树 2,4,#,#,# 也出现多次。按节点数更多优先输出所以先输出 2,4,#,#,#再输出 4,#,#。示例2输入5,7,7输出7,#,#说明左右两个叶子节点 7 的结构和值都相同因此形成重复子树。思路典型的DFS树类型题目先把输入的层序遍历还原成一棵二叉树然后对整棵树做一次深度优先遍历。遍历到某个节点时不只是看这个节点本身而是把“以这个节点为根的整棵子树”序列化成一个字符串。序列化时按照题目要求使用前序遍历同时把空节点也记录成 #这样才能把子树的结构信息和节点值信息一起保留下来。比如叶子节点 4 会被序列化成 4,#,#如果另一处也得到完全一样的结果就说明这两棵子树是重复的。1.在遍历过程中用一个哈希表统计每种子树序列化结果出现了多少次。2.只要某个序列化结果出现次数大于 1就说明它对应的是重复子树。与此同时再额外记录每种重复子树的节点个数方便最后排序输出。3.等整棵树遍历完成后把所有出现次数大于 1 的序列化结果取出来按照“节点数降序、序列化字符串升序”的规则排序最后逐行输出即可。4.如果没有任何序列化结果重复出现就输出空内容。Codeimport sys from collections import deque class TreeNode: def __init__(self, val: str) - None: # 当前节点存储的值按字符串处理。 self.val val # 左右子节点初始化为空。 self.left None self.right None def build_tree(tokens: list[str]): # 空输入或根节点为 # 时表示整棵树为空。 if not tokens or tokens[0] #: return None # 先创建根节点。 root TreeNode(tokens[0]) queue deque([root]) idx 1 # 输入是“带 # 的真实层序遍历”所以要按队列顺序恢复二叉树。 while queue and idx len(tokens): node queue.popleft() # 处理左孩子。 if idx len(tokens) and tokens[idx] ! #: node.left TreeNode(tokens[idx]) queue.append(node.left) idx 1 # 处理右孩子。 if idx len(tokens) and tokens[idx] ! #: node.right TreeNode(tokens[idx]) queue.append(node.right) idx 1 return root def solve(text: str) - str: raw text.strip() # 没有输入时直接输出空内容。 if not raw: return # 按逗号拆分层序输入并去掉每段两侧空白。 tokens [part.strip() for part in raw.split(,)] root build_tree(tokens) if root is None: return # 统计每种子树序列化出现的次数。 freq {} # 记录每种序列化对应的节点个数便于最终排序。 node_count {} def dfs(node): # 空节点固定序列化为 #节点数为 0。 if node is None: return #, 0 # 递归处理左右子树。 left_serial, left_count dfs(node.left) right_serial, right_count dfs(node.right) # 按题意使用前序序列化根,左,右。 serial f{node.val},{left_serial},{right_serial} count 1 left_count right_count # 记录出现次数和节点数。 freq[serial] freq.get(serial, 0) 1 node_count[serial] count return serial, count dfs(root) # 只保留真正重复的子树也就是出现次数大于 1 的序列化结果。 duplicates [serial for serial, count in freq.items() if count 1] # 先按节点数降序再按序列化字符串升序排序。 duplicates.sort(keylambda serial: (-node_count[serial], serial)) # 题目要求逐行输出没有结果则输出空内容。 return \n.join(duplicates) if __name__ __main__: print(solve(sys.stdin.read()))JSconst fs require(fs); class TreeNode { constructor(val) { // 当前节点值。 this.val val; // 左右子节点。 this.left null; this.right null; } } function buildTree(tokens) { // 空输入或根节点为 # 时整棵树为空。 if (tokens.length 0 || tokens[0] #) { return null; } // 创建根节点并按层恢复树结构。 const root new TreeNode(tokens[0]); const queue [root]; let idx 1; // 输入是带 # 的真实层序遍历所以按队列顺序给每个节点挂孩子。 while (queue.length 0 idx tokens.length) { const node queue.shift(); // 恢复左孩子。 if (idx tokens.length tokens[idx] ! #) { node.left new TreeNode(tokens[idx]); queue.push(node.left); } idx; // 恢复右孩子。 if (idx tokens.length tokens[idx] ! #) { node.right new TreeNode(tokens[idx]); queue.push(node.right); } idx; } return root; } function solve(text) { const raw text.trim(); // 没有输入时输出空内容。 if (raw.length 0) { return ; } // 解析逗号分隔输入并去掉每段两侧空白。 const tokens raw.split(,).map(s s.trim()); const root buildTree(tokens); if (root null) { return ; } // 统计每种子树序列化出现的次数。 const freq new Map(); // 记录每种序列化对应的节点数。 const nodeCount new Map(); function dfs(node) { // 空节点固定序列化为 #节点数记为 0。 if (node null) { return { serial: #, count: 0 }; } // 递归处理左右子树。 const left dfs(node.left); const right dfs(node.right); // 按题意使用前序序列化。 const serial ${node.val},${left.serial},${right.serial}; const count 1 left.count right.count; // 记录出现次数和节点数。 freq.set(serial, (freq.get(serial) || 0) 1); nodeCount.set(serial, count); return { serial, count }; } dfs(root); // 只保留真正重复的子树。 const duplicates []; for (const [serial, count] of freq.entries()) { if (count 1) { duplicates.push(serial); } } // 按题意排序节点数降序序列化升序。 duplicates.sort((a, b) { if (nodeCount.get(a) ! nodeCount.get(b)) { return nodeCount.get(b) - nodeCount.get(a); } return a.localeCompare(b); }); // 逐行输出没有重复则输出空内容。 return duplicates.join(\n); } console.log(solve(fs.readFileSync(0, utf8)));【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。