自己做网站难,东莞理工学院教务处,短链接在线生成器,平面设计师务所Problem: 1457. 二叉树中的伪回文路径 思路
首先想用最暴力的深度优先DFS#xff0c;使用traversePaths方法来遍历二叉树并存储所有路径。该方法接收当前节点、当前路径和路径列表作为参数。当到达叶子节点时#xff0c;将当前路径添加到路径列表中。
然后#xff0c;我们… Problem: 1457. 二叉树中的伪回文路径 思路
首先想用最暴力的深度优先DFS使用traversePaths方法来遍历二叉树并存储所有路径。该方法接收当前节点、当前路径和路径列表作为参数。当到达叶子节点时将当前路径添加到路径列表中。
然后我们遍历每条路径并调用isPseudoPalindromic方法来判断路径是否为伪回文。更新结果并输出。
这样能跑二叉树体量较小的用例代码中使用了一个路径列表paths来存储所有的路径这也会占用大量的内存空间特别是当二叉树非常大时路径数量可能非常庞大导致内存消耗过大。
如何优化
因为节点的值只可能为1到9因此可以用一个长度为10的数组counter来记录路径中各个值出现的次数。 并且用深度优先搜索的方式来遍历所有叶子定义函数dfs输入为接下去要访问的节点和记录了根节点到该节点不含)的路径上各个值出现的次数的数组counter并返回一个整数用来表示根节点到以该节点为祖先的叶子节点的所有路径中伪回文路径的数目。
解题方法
首先判断该节点是否为空如果为空则返回0。接下来更新counter表示访问到了当前节点。然后判断当前节点是否为叶子节点如果是按照isPseudoPalindromic方法判断counter 中的所有元素是否能构成一个回文序列。如果不是叶子节点则分别访问当前节点的两个子节点将返回值求和作为自己的返回值。最后在返回之前需要撤销一开始对counter的更新。对根节点root进行dfs的调用返回即可。
复杂度
时间复杂度: O ( C ∗ n ) O(C*n) O(C∗n) C 是节点中不同元素的数量n 是二叉树的节点数。二叉树中的每个元素都会被访问到每次访问到叶子节点判断是否为伪回文路径消耗 O ( C ) O(C) O(C)。
空间复杂度: O ( n ) O(n) O(n) 深度优先搜索的深度最深为n
Code
暴力DFS大体量二叉树会爆内存
class Solution {public int pseudoPalindromicPaths (TreeNode root) {//定义每条路径和当前路径ListListInteger paths new ArrayList();ListInteger currentpath new ArrayList();//调用辅助方法遍历路径并存储traversePaths(root,paths,currentpath);int res 0;//遍历每条路径for(ListInteger path:paths){//判断是否回文写个函数if(isPseudoPalindromic(path)){res;}}return res;}private void traversePaths(TreeNode node,ListListInteger paths,ListInteger currentpath){if(node null){return;}currentpath.add(node.val);//将当前节点的值添加到当前路径// 到达叶节点时将当前路径添加到路径列表中if (node.left null node.right null) {paths.add(new ArrayList(currentpath));}//递归遍历左子树和右子树traversePaths(node.left,paths,currentpath);traversePaths(node.right,paths,currentpath);//移除当前节点的值回到上一层currentpath.remove(currentpath.size() - 1);}private boolean isPseudoPalindromic(ListInteger path){int[] counts new int[10]; // 用于计数每个数字0-9出现的次数// 统计路径中每个数字的出现次数for (int num : path) {counts[num];}int oddCount 0; // 奇数次出现的数字的数量// 检查路径是否是伪回文的for (int count : counts) {if (count % 2 ! 0) { // 如果数字出现次数为奇数oddCount;}} return oddCount 1; // 如果最多只有一个数字出现次数为奇数则返回true}
}DFS更新counter题解
class Solution {public int pseudoPalindromicPaths (TreeNode root) {int[] counter new int[10];return dfs(root,counter);}public int dfs(TreeNode node, int[] counter){if(node null){return 0;}counter[node.val];int res 0;if(node.left null node.right null){if(isPseudoPalindrome(counter)){res 1;}}else{res dfs(node.left,counter) dfs(node.right,counter);}counter[node.val]--;return res;}public boolean isPseudoPalindrome(int[] counter){int odd 0;for(int value : counter){if(value % 2 1){odd;}}return odd 1;}
}
