X 的平方根 && 对称二叉树 && 反转字符串

X 的平方根

这是力扣第 69 题

给你一个非负整数 x ，计算并返回  x  的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

解题思路

这是一道简单题，第一眼看过去，是不是觉得和上次那道 Pow（x，n）很像，但是又不完全一样。在这里题目中已经指明了不能使用库函数，因此这题的本质就和 Pow（x，n）那道题一样，让我们自己手写一个函数来解决相关问题。有了那次的经验，写这种函数的题目应该是十分轻松的。我们只需找到两个关键点，一是对应什么函数，二是如何运行出结果。

二分法

可能很多人都没能想到，这是一道可以用二分查找的题目，但是这题用二分法来解决是最好的思路了。二分法就不用再做介绍了吧，之前已经讲过很多次了。二分法的精髓在于判断中间值大于左边还是大于右边以及是否取中间值，这些在之前的文章里已经讲得很清楚了，新来的小伙伴们可以再去看看。

对于这题而言，我们首先需要从数组的中间元素开始查找，如果这个中间元素是我们所需要的目标值，就结束查找，否则就继续查找。如果目标值小于或者大于中间元素，则在数组中小于或者大于中间元素的剩下区域里继续查找，并重复前面的操作。这就是二分法在此题里的思路。

相关代码如下：

var mySqrt = function(x) {
    if (x < 2) return x
    let left = 1;
    let right = Math.floor(x / 2);
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (mid * mid === x) return mid
        if (mid * mid < x) {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    return right

对称二叉树

这是力扣 101 题

给你一个二叉树的根节点  root ， 检查它是否轴对称。

解题思路

经历了数组、链表的环节，现在来看看二叉树相关的题目。 先来介绍一下二叉树吧，二叉树有两种主要的形式：满二叉树和完全二叉树。 其实很多人会分不清楚满二叉树和完全二叉树。最开始接触的时候我也会分不清楚，但是这不重要，重要的是不知道的时候我就会去查找它们的概念，对比它们的区别，来加强对它们的印象，最后通过多做题来熟能生巧。

看到这道题目，首先我们可以考虑将题目意思转换一下。一个树是对称的，所以它的左右子树也一定是对称的，进而就可以推导出当根节点的值是相同的时候，一个树的右子树和另一个树的左子树对称。因此，这里将引出递归法解决此题。

递归法

递归法在二叉树的题目中很常用，递归思想在二叉树中极其普遍，所以需要掌握。接下来介绍一下此题的解题思路：如果两个子树都为 null，是对称的；如果两个子树都存在，则需要 root 值相同；如果一个子树存在一个不存在，肯定是不对称的；如果传入的 root 就是 null，则是对称的，否则，判断它的左右子树是否满足对称。

相关代码如下：

const isSymmetric = (root) => {
    const check = (left, right) => {
        if (left == null && right == null) {
           return true;
        }
        if (left && right) {
            return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
        }
        return false;
    };

    if (root == null) {
        return true;
    }
    return check(root.left, root.right);
};

对于二叉树的题目，我的建议是多看看关于不同的二叉树的概念以及在写题的过程中多画图，这样会使思路更清晰。

反转字符串

这是力扣 344 题

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

解题思路

这是一道非常简单的题目，写过这道题的人也是非常多，因此这道题也有非常多的解法。所以接下来将介绍一些我个人认为比较经典的解法。

API 解法

这个解法属于特别离谱的那种，我们直接调用 JS 自带的 API 即可。

相关代码如下：

var reverseString = function(s) {
    s.reverse();
};

一行代码，就能解决这题，大家说离谱不离谱。这就是 JS 的魅力。但是使用 API 解题并不是终点，只是解题的一个过程（大家就当图一乐，实在想不到其他方法再去选择用它）。接下来就来介绍一下更合理的解法。

双指针法

调用 API 固然很快乐，但是对思维得不到充分的锻炼。其实这道题不难想到可以用双指针法。双指针法太常用了，所以请大家务必要掌握。对于长度为 N 的即将被反转的字符数组，我们来观察一下反转前后下标的变化。假设反转前字符数组为 s[0]，s[1]，...s[N - 1]，那么反转后字符数组为 s[N - 1]，s[N - 2]，... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律。

所以对于这题，双指针的思路如下：

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right，交换 s[left] 和 s[right]；
• 当 left >= right，反转结束，返回字符数组即可

相关代码如下：

var reverseString = function(s) {
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    [s[start], s[end]] = [s[end], s[start]];
    start++;
    end--;
  }
  return s;
};