魔法网站小程序开发,专门做外贸的的网站有哪些,建筑网片计算公式详解,如何建立自己的网络销售【LetMeFly】1457.二叉树中的伪回文路径#xff1a;深度优先搜索(DFS) 位运算优化
力扣题目链接#xff1a;https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/
给你一棵二叉树#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「…【LetMeFly】1457.二叉树中的伪回文路径深度优先搜索(DFS) 位运算优化
力扣题目链接https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/
给你一棵二叉树每个节点的值为 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, 105] 内1 Node.val 9
方法一深度优先搜索(DFS) 位运算优化
首先这道题组成“回文序列”时每个数的顺序可变。因此不难发现一个序列可以组成回文序列 等价于 这个序列要么每个数都出现了偶数次要么只有一个数出现了奇数次其他数都出现了偶数次。
因此我们只深度优先搜索使用一个大小为 10 10 10的数组节点中每个数的范围是1-9存储每个数出现的次数。当搜索到叶节点时看数组中元素出现的次数是否满足上方要求即可。
如何使用位运算进行优化呢我们可以使用一个数的低 10 10 10位来存储“某个数出现了奇数次还是偶数次”这一信息。若出现奇数次则这一位为1出现偶数次则这一位为0。
这样在遍历过程中若当前节点值为 a a a就将 m a s k mask mask异或上 ( 1 a ) (1a) (1a)。
最终看 m a s k mask mask是否最多有一个 1 1 1的时候可以借助lowbit的思想。若KaTeX parse error: Expected EOF, got at position 14: mask (mask ̲ -mask)则mask二进制下最多有1个1。 6 ( 110 ) 2 6(110)_2 6(110)2 l o w b i t ( 6 ) ( 10 ) 2 lowbit(6)(10)_2 lowbit(6)(10)2 12 ( 1100 ) 2 12(1100)_2 12(1100)2 l o w b i t ( 12 ) ( 100 ) 2 lowbit(12)(100)_2 lowbit(12)(100)2
以上。
时间复杂度 O ( n ) O(n) O(n)其中 n n n是二叉树节点个数空间复杂度 O ( n ) O(n) O(n)。若二叉树退化成一个直链则递归消耗 O ( n ) O(n) O(n)的空间
AC代码
C
class Solution {
private:int ans;void dfs(TreeNode* root, int mask) {mask ^ (1 root-val);if (!root-left !root-right) {ans __builtin_popcount(mask) 2;}if (root-left) {dfs(root-left, mask);}if (root-right) {dfs(root-right, mask);}}public:int pseudoPalindromicPaths (TreeNode* root) {ans 0;dfs(root, 0);return ans;}
};Python
class Solution:def dfs(self, root: TreeNode, mask: int) - None:mask ^ (1 root.val)if not root.left and not root.right:self.ans mask (mask -mask)if root.left:self.dfs(root.left, mask)if root.right:self.dfs(root.right, mask)def pseudoPalindromicPaths (self, root: TreeNode) - int:self.ans 0self.dfs(root, 0)return self.ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134617854
