1457. Pseudo-Palindromic Paths in a Binary Tree¶
题目信息¶
- 题号:
1457
- 难度:
Medium
- 主题:
二叉树、深度优先搜索、奇偶计数、位掩码
- 原题:
- 重点:
根到叶路径上的节点值若至多一种出现奇数次,则这些值可重排成回文序列
题目重述¶
给定一棵二叉树,节点值位于 1 到 9。对于每条从根节点到叶节点的路径,收集路径上的节点值。
若这些值经过任意重排后能够形成回文序列,则该路径为伪回文路径。请返回所有伪回文根到叶路径的数量。
树中节点数位于 [1,10^5]。
自建示例¶
只有一条路径满足奇数频次条件:
输入:root = [2,2,3]
输出:1
解释:左侧路径值为 [2,2],可组成回文;右侧路径 [2,3] 有两种奇数频次,不能组成回文。
单节点路径必然可以组成回文:
输入:root = [7]
输出:1
解释:长度为一的序列本身就是回文。