目录

题目

思路

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.如果没有任何序列化结果重复出现，就输出空内容。

Code

import 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(key=lambda serial: (-node_count[serial], serial))

    # 题目要求逐行输出，没有结果则输出空内容。
    return "\n".join(duplicates)


if __name__ == "__main__":
    print(solve(sys.stdin.read()))

JS

const 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机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。