字符串相加 && 二叉树的最小深度 && 平衡二叉树

字符串相加

这是力扣第 415 题

给定两个字符串形式的非负整数  num1 和 num2 ，计算它们的和并同样以字符串形式返回。 你不能使用任何内建的用于处理大整数的库（比如 BigInteger），  也不能直接将输入的字符串转换为整数形式。

解题思路

这是一道简单题，比较容易想清楚如何解决它。从简单的层面理解，我们可以把字符串相加看成是整数相加，进而可以得出第一种思路 —— 将字符串转换成整数进行相加。除此之外，还可以用双指针来实现相加，第二种思路双指针法就这样产生了。接下来就来介绍这两种方法。

字符串转换成数字

这种方法十分简单且容易理解，将字符串转换为数字，再对它进行相加，最终返回结果的时候再转换为字符串类型即可。思路方面上没有什么难点可言。

相关代码如下：

var addStrings = function (num1, num2) {
num1 = BigInt(num1)
num2 = BigInt(num2)
return String(num1 + num2)
};

双指针法

用双指针来模拟两数计算，从而达到字符串相加的效果。整体思路如下：

首先分别创建两个指针 i 和 j，指针 i 指向 nums1 末位数字，指针 j 指向 nums2 末位数字。 然后用 carry 来记录进位值，没有进位则为 0。 如果在遍历过程中产生进位，则让当前数字变为 (i+j)%10 的值。 如果在遍历过程中 nums1 或 nums2 当前已经没有数字了，就用 0 来进行补位。 最后返回最终相加的结果即可。

var addStrings = function(num1, num2) {
    let i = num1.length - 1,
        j = num2.length - 1,
        carry = 0,
        ans = [];
    while(i >= 0 || j >= 0 || carry !== 0){
        let c1 = i >= 0 ? num1.charAt(i) - '0' : 0,
            c2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        let sum = c1 + c2 + carry;
        ans.push(sum % 10);
        carry = Math.floor(sum / 10);
        i--;
        j--;
    }
    return ans.reverse().join('');
};

二叉树的最小深度

这是力扣 111 题

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明： 叶子节点是指没有子节点的节点。

解题思路

之前看过一道二叉树最大深度的题目，现在这是一道二叉树最小深度的题目。第一眼看过去感觉两者都差不多，不过其实从本质上看还是差不少的。用前序遍历和后序遍历都可以解决此题，前序求的是深度，后序求的是高度。但是这里需要注意一点题目中所定义的最小深度的概念，最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 因此如果某一侧没有子节点，这种情况是不算的。

递归解法

二叉树的问题都有递归性，因此看到二叉树的题目，二话不说就是递归解法，递归解法的整体思路如下：

• 左子树为空，返回右子树最小深度+1
• 右子树为空，返回左子树最小深度+1
• 左右子树均不空，返回左子树、右子树最小深度的最小值+1
• 根节点为空返回 null

这样仅仅靠看会有点不好理解，因此直接来看代码吧，如果还是不好理解的话可以画图表示一下。

相关代码如下：

var minDepth = function(root) {
    if(!root) return 0;
    if(root.left === null) {
        return minDepth(root.right) + 1
    }
    if(root.right === null) {
        return minDepth(root.left) + 1
    }
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

这种解法又称为广度优先遍历，广度优先遍历是遍历整棵树，时间复杂度为 O(n)，空间复杂度也是 O(n)，n 为树的节点数量。如果可以找到某一个叶子节点，直接返回这个叶子节点的深度，这就是广度优先遍历。

平衡二叉树

这是力扣 110 题

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

解题思路

这是一道简单题，题目中给了高度平衡的定义：一个二叉树每个节点的左右子树的高度差的绝对值不超过 1。

首先我们要先明确两个概念 —— 二叉树节点的深度和高度。很多人会对这两个概念模棱两可，就分不清满二叉树和完全二叉树一样。

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

另外，求二叉树深度可以从上到下去查，需要前序遍历；求高度只能从下到上去查，需要后序遍历。了解清楚这些，下面来介绍一下相关解题思路了。

暴力递归

暴力解法的解题思路如下：

首先遍历二叉树，然后对每一个节点计算左右的最大高度，计算一棵二叉树的最大深度需要递归遍历这棵二叉树的所有节点。所以如果对每个节点都进行一遍遍历，会增加时间复杂度。

相关代码如下：

var isBalanced = function (root) {
  let flag = true;
  const maxDepth = (root) => {
    if (root == null) return 0;
    if (!flag) return;
    let leftMaxDepth = maxDepth(root.left);
    let rightMaxDepth = maxDepth(root.right);
    if (Math.abs(rightMaxDepth - leftMaxDepth) > 1) {
      flag = false;
    }
    return 1 + Math.max(leftMaxDepth, rightMaxDepth);
  };
  maxDepth(root);
  return flag;
};

优化递归

由于暴力递归复杂度较高，因此有了如下优化递归的方案。

通过后序遍历来遍历二叉树，并返回子树最大高度，从而判定每个子树是不是平衡树。如果平衡，则通过它们的高度来判断父节点是否平衡，并计算父节点的高度。

相关代码如下：

var isBalanced = function (root) {
    return balanced(root) !== -1
};
var balanced = function (node) {
    if (!node) return 0
    const left = balanced(node.left)
    const right = balanced(node.right)
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1
    }
    return Math.max(left, right) + 1
}