LeetCode(力扣)答案解析（八）

[Checkson]

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例1：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例2：

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

解法一（深度优先搜索 + 中序遍历）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
     var arr = [],
        st = [],
        p = root;
    while (p != null || st.length != 0) {
        while(p != null){
          st.push(p);
          p = p.left;
        }
        p = st.pop();
        arr.push(p.val);
        p = p.right;
    }
    return arr[k - 1];
};

解法二（递归）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    var list = [];
    order(root,list);
    return list[k-1];
};
function order (root, list) {
    if (!root) {
        return;
    }
    order(root.left, list);
    list.push(root.val);
    order(root.right, list);
}

解析：

无论是递归方法还是非递归方法，其基本思路都是通过中序遍历搜索二叉树后，得到了从小到大的序列，然后直接取出下标为 k - 1 的元素。

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例1：

输入: num1 = "2", num2 = "3"
输出: "6"

示例2：

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

• num1 和 num2 的长度小于110。
• num1 和 num2 只包含数字 0-9。
• num1 和 num2 均不以零开头，除非是数字 0 本身。
• 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解：

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    var arr1 = num1.split('').reverse(),
        arr2 = num2.split('').reverse();
    var res = [],
        tmp = 0;
    for (var i = 0, len1 = arr1.length; i < len1; i++) {
        for (var j = 0, len2 = arr2.length; j < len2; j++) {
            var a = parseInt(arr1[i]),
                b = parseInt(arr2[j]),
                multi = a * b,
                val = parseInt(res[i + j] || 0);
            val += (multi + tmp);
            if (typeof res[i + j] === 'undefined') {
                res.push(val % 10 + '');
            } else {
                res[i + j] = (val % 10 + '');
            }
            tmp = parseInt(val / 10);
        }
        if (tmp) {
            res.push(tmp + '');
            tmp = 0;
        }
    }
    // 去除多余的0
    var isValid = true;
    for (var i = res.length - 1; i >= 0; i--) {
        if (i === 0) {
            continue;
        } else if (res[i] === '0' && isValid) {
            res.splice(i, 1);
        } else if (res[i] !== '0') {
            isValid = false;
        }
    }
    return res.reverse().join('');
};

2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    var ans = null,
        trail = null,
        node = null,
        tmp = 0;
    while (l1 != null || l2 != null) {
        var val = tmp;
        if (l1 != null) {
            val += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            val += l2.val;
            l2 = l2.next;
        }
        var node = new ListNode(val % 10);
        tmp = parseInt(val / 10);
        if (ans) {
            trail.next = node;
            trail = node;
        } else {
            ans = node;
            trail = node;
        }
    }
    if (tmp) {
        node = new ListNode(tmp);
        trail.next = node;
    }
    return ans;
};