自己动手制作网站,模板之家会员,易企秀在线制作免费,万能搜索网站1. 题目
给你一棵二叉树#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的#xff0c;当它满足#xff1a;路径经过的所有节点值的排列中#xff0c;存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的当它满足路径经过的所有节点值的排列中存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1
输入root [2,3,1,3,1,null,1]
输出2
解释上图为给定的二叉树。总共有 3 条从根到叶子的路径
红色路径 [2,3,3] 绿色路径 [2,1,1] 和路径 [2,3,1] 。在这些路径中只有红色和绿色的路径是伪回文路径因为红色路径 [2,3,3] 存在回文排列 [3,2,3] 绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。示例 2
输入root [2,1,1,1,3,null,null,null,null,null,1]
输出1
解释上图为给定二叉树。总共有 3 条从根到叶子的路径
绿色路径 [2,1,1] 路径 [2,1,3,1] 和路径 [2,1] 。这些路径中只有绿色路径是伪回文路径因为 [2,1,1] 存在回文排列 [1,2,1] 。示例 3
输入root [9]
输出1提示
给定二叉树的节点数目在 1 到 10^5 之间。
节点值在 1 到 9 之间。来源力扣LeetCode 链接https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
用int的9个bit来表示数字1-9的奇偶个数递归进行处理到达叶子节点时计算int的1的位数要1则该路径满足题意
class Solution {int count 0;
public:int pseudoPalindromicPaths (TreeNode* root) {dfs(root, 0);return count;}void dfs(TreeNode* root, int state){int m root-val;if((statem)1)//为1state ~(1m);//改为0elsestate | (1m);//该位是0则改为1if(!root-left !root-right){ //叶子节点int odd 0;for(int i 1; i 9; i)if((statei)1)odd;if(odd 1)count;return;}if(root-left)dfs(root-left, state);if(root-right)dfs(root-right, state);}
};248 ms 107.1 MB
