652.寻找重复的子树.md

652.寻找重复的子树

/*
 * @lc app=leetcode.cn id=652 lang=typescript
 *
 * [652] 寻找重复的子树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {}
// @lc code=end

解法 1: 哈希表

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
  if (!root) return []
  const map = new Map<string, number>(),
    res: TreeNode[] = [],
    id: number[] = []
  let idx = 0
  const dfs = (node: TreeNode): number => {
    let key = node.val + ''
    if (node.left) key += ',' + dfs(node.left)
    else key += ','
    if (node.right) key += ',' + dfs(node.right)
    else key += ','
    if (!map.has(key)) {
      id[idx] = 0
      map.set(key, idx++)
    }

    if (id[map.get(key)!]++ === 1) res.push(node)
    return map.get(key)!
  }
  dfs(root)
  return res
}

Case

test.each([
  { input: { root: [1, 2, 3, 4, null, 2, 4, null, null, 4] }, output: [[2, 4], [4]] },
  { input: { root: [2, 1, 1] }, output: [[1]] },
  { input: { root: [2, 2, 2, 3, null, 3, null] }, output: [[2, 3], [3]] },
])('input: root = $input.root', ({ input: { root }, output }) => {
  expect(findDuplicateSubtrees(BinaryTree.deserialize(root))).toIncludeSameMembers(output.map(BinaryTree.deserialize))
})