最长回文串 && 无重复字符的最长子串 && 二叉树的所有路径

最长回文串

这是力扣 409 题

给定一个包含大写字母和小写字母的字符串  s ，返回   通过这些字母构造成的 最长的回文串  。 在构造过程中，请注意 区分大小写 。比如  "Aa"  不能当做一个回文字符串。

解题思路

第一眼看过去是不是感觉这题在哪里见过，仔细一想，原来想到的是最长回文子串的那道题目。最长回文串和最长回文子串，虽然只有一字之差，但是要求返回的最终结果却是大不相同。因此这是两道看起来有点像但是实际完全不同的题目。

拿到这道题，我们首先应该想如何能成为最长回文串？其实不难发现，只有当为偶数个字符且中间一个单独奇数的才能组成最长回文串，想清楚这个，接下来就来介绍相关思路了。

找规律法

这种思路就是使用上面提到的规律来实现效果，具体思路是这样：我们将所有偶个数的字符总个数计数并保存，然后判断是否还有字符没被统计到，如果有就加一，否则就返回最终结果。

相关代码如下：

var longestPalindrome = function(s) {
    var countObj = {};
    var res = 0;
    for(var i=0;i<s.length;i++){
        if(!countObj[s[i]]){
            countObj[s[i]] = 1;
        }else{
            res +=2;
            delete countObj[s[i]];
        }
    }
    if(s.length > res){
        res +=1;
    }
    return res;
};

map 法

其实对这题换一种思考的方法的话，我们可以把它想像成比较有多少对相同的字符即可。所以当有相同的字符存在，就相当于找到了回文字符。可能这么说不太好理解，结合代码一起来看或许更容易明白。

相关代码如下：

var longestPalindrome = function(s) {
   let m=new Map();
   for(let i=0;i<s.length;i++){
      m.set(s[i],m.has(s[i]) ? m.get(s[i])+1 : 1);
   }
   let ans=0;
   let flag=false;  //是否存在奇数个，中间可以是奇数个
   for(let val of m.values()){
      if (val%2===0) {
         ans+=val;
      }else{
         ans+=val-1;
         flag=true;
      }
   }
   if (flag) {
      ans+=1;
   }
   return ans;
};

回文串的特点是成双成对，利用这个特点可以很好的理解这种思路。

无重复字符的最长子串

这是力扣第 3 题

给定一个字符串  s ，请你找出其中不含有重复字符的  最长子串 的长度。

解题思路

这是一道中等难度的题目，算是很多人心中的回忆了吧（毕竟是力扣第三题，很多人的刷题记忆都是从这里开始的）。这题说难也不难，说简单也不简单。因为从通过率上来看，貌似不是很理想，但是从题意上看，感觉又不是很难。所以这题值得探讨一下。接下来将介绍一下以下几种解题思路。

双指针法

首先最容易想到的思路是双指针法，双指针法讲了这么多次，想必大家都很对它比较熟悉了吧。对于这题而言，创建两个 left 和 right 指针, 当让 right 指针前移的时候, 就去检测 max 的值；当让 left 指针前移的时候，就直接进入下一个循环。当两个指针相减大于 max 时，就返回此时的 max 值。

相关代码如下：

var lengthOfLongestSubstring = function(str) {
    if (str.length <= 1) {return str.length}
      let left = 0
      let right = 1
      let max = 0
      let temp
      while(right<str.length){
        temp = str.slice(left, right)
        if (temp.indexOf(str.charAt(right)) > -1) {
          left++
          continue
        } else {
          right++
        }
        if (right - left > max) { max = right - left }
      }
      return max
};

数组

字符串相关的题目用数组思想来解决也是常用的思路。用数组解决此题的思路是将没有重复的值按顺序放入到新数组 temp 中，当出现重复数字时，就以该数字后面的元素为起始头往下寻找。整体思路如下：

• 遍历数组，将数组中不重复的值去除
• 如果有重复值出现，去除第一个元素，将刚才重复的值重新导入数组
• 最后通过 Math 函数选出两个值中较大的那个值并返回最终结果

相关代码如下：

var lengthOfLongestSubstring = function(s) {
    let res = 0, temp = []
    for (let i=0;i<s.length;i++) {
        if (temp.indexOf(s[i]) == -1) {
            temp.push(s[i])
        } else {
            temp.shift()
            i--
            continue
        }
        res = Math.max(res, temp.length)
    }
    return res
};

二叉树的所有路径

这是力扣 257 题

给你一个二叉树的根节点  root ，按  任意顺序 ，返回所有从根节点到叶子节点的路径。 叶子节点  是指没有子节点的节点。

解题思路

题目要求我们求根节点到叶子节点的路径，所有很显然是一道前序遍历的题目，题目不难，比较简单，也比较容易理解。之所以用前序遍历，是因为这样方便父节点指向叶子节点，从而找到相应的路径。接下来就来介绍两种关于此题的解法思路。

深度优先搜索

第一种是深度优先遍历，对于这种遍历方式，我们需要考虑父节点和叶子节点。整体思路大概是这样：如果当前节点是叶子节点，则在当前路径末尾添加该节点，这样就是一条从根节点到叶子节点的路径；如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个叶子节点。

相关代码如下：

var binaryTreePaths = function(root) {
    const paths = [];
    const construct_paths = (root, path) => {
        if (root) {
            path += root.val.toString();
            if (root.left === null && root.right === null) {
                paths.push(path);
            } else {
                path += "->";
                construct_paths(root.left, path);
                construct_paths(root.right, path);
            }
        }
    }
    construct_paths(root, "");
    return paths;

广度优先遍历

第二种是广度优先遍历，广度优先遍历就是创建一个队列，然后存储节点到根的信息。对于队列而言，如果队列的首节点是叶子节点，则将它对应的路径加入到答案中。如果它不是，则将它的叶子节点加入到队列的末尾。从某种意义上看，它在思路上和深度优先遍历有着异曲同工之妙。

相关代码如下：

var binaryTreePaths = function(root) {
	const res = [];
	function findNext(root, route) {
		if(!root) return;
		if(!root.left && !root.right) res.push(route);
		findNext(root.left, root.left ? route + '->' + root.left.val : route);
		findNext(root.right, root.right ? route + '->' + root.right.val : route);
	}
	findNext(root, (root && root.val) + '');
	return res;
}