Lstmxx的空间

1457. 二叉树中的伪回文路径

给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。

请你返回从根到叶子节点的所有路径中   伪回文   路径的数目。

链接

/**
 * 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 pseudoPalindromicPaths(root: TreeNode | null): number {
  let res = 0;
  if (root === null) return res;
  function dfs(node: TreeNode, pathMap: Record<number, number>) {
    if (node === null) {
      return;
    }
    if (!pathMap[node.val]) {
      pathMap[node.val] = 0;
    }
    pathMap[node.val] += 1;
    if (node.left === null && node.right === null) {
      const vals: number[] = Object.values(pathMap);
      const len = vals.length;
      const oneArr: number[] = [];
      let total = 0;
      for (let i = 0; i < len; i++) {
        const count = vals[i];
        if (count % 2 === 1) {
          oneArr.push(count);
        }
        total += count;
      }
      if (oneArr.length === 0 || (oneArr.length === 1 && total % 2 === 1)) {
        res++;
      }
      return;
    }
    dfs(node.left, Object.assign({}, pathMap));
    dfs(node.right, Object.assign({}, pathMap));
  }
  dfs(root, {});
  return res;
}