1. 題目

給你一棵二叉樹(shù)，每個(gè)節(jié)點(diǎn)的值為 1 到 9 。我們稱(chēng)二叉樹(shù)中的一條路徑是 「?jìng)位匚摹沟?#xff0c;當(dāng)它滿(mǎn)足：路徑經(jīng)過(guò)的所有節(jié)點(diǎn)值的排列中，存在一個(gè)回文序列。

請(qǐng)你返回從根到葉子節(jié)點(diǎn)的所有路徑中 偽回文 路徑的數(shù)目。

示例 1：

輸入：root = [2,3,1,3,1,null,1] 輸出：2 解釋：上圖為給定的二叉樹(shù)。總共有 3 條從根到葉子的路徑： 紅色路徑 [2,3,3] ，綠色路徑 [2,1,1] 和路徑 [2,3,1] 。在這些路徑中，只有紅色和綠色的路徑是偽回文路徑，因?yàn)榧t色路徑 [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 解釋：上圖為給定二叉樹(shù)。總共有 3 條從根到葉子的路徑： 綠色路徑 [2,1,1] ，路徑 [2,1,3,1] 和路徑 [2,1] 。這些路徑中只有綠色路徑是偽回文路徑，因?yàn)?[2,1,1] 存在回文排列 [1,2,1] 。示例 3： 輸入：root = [9] 輸出：1提示： 給定二叉樹(shù)的節(jié)點(diǎn)數(shù)目在 1 到 10^5 之間。 節(jié)點(diǎn)值在 1 到 9 之間。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 用int的9個(gè)bit來(lái)表示數(shù)字1-9的奇偶個(gè)數(shù)
• 遞歸進(jìn)行處理，到達(dá)葉子節(jié)點(diǎn)時(shí)，計(jì)算int的1的位數(shù)要<=1則該路徑滿(mǎn)足題意

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((state>>m)&1)//為1state &= ~(1<<m);//改為0elsestate |= (1<<m);//該位是0，則改為1if(!root->left && !root->right){ //葉子節(jié)點(diǎn)int odd = 0;for(int i = 1; i <= 9; ++i)if((state>>i)&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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1457. 二叉树中的伪回文路径（位运算+递归）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。