合并K个升序链表 && 合并二叉树 && 二叉树的最大深度

合并 K 个升序链表

这是力扣 23 题

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路

这是一道困难题，所以是很有质量的，可以好好研究一下。在没写这题之前，我介绍过合并两个升序链表的题目，就是将两个链表合并成一个链表。而此题则是将 K 个链表合并成一个链表，所以更具有挑战性。一旦做出来了这题，合并类型的题目就没啥问题了，可以直接套模板了。接下来就来介绍几种解题思路。

数组法

第一种很容易想到的思路就是数组法，在合并两个链表的时候，我用的就是这种方法。将链表遍历，并将遍历所得的值全部放入数组中，之后对数组重新排序，将排序后的数组转换成链表即可，思路清晰简单。

相关代码如下：

var mergeKLists = function(lists) {
    function transform(l, arr) {
        while(l) {
            arr.push(l.val);
            l = l.next;
        }
    }
    let arr = [];
    let res = new ListNode(null);

    lists.map(item => transform(item, arr));

    arr.sort((a, b) => a - b);
    //数组转链表
    for (let i = arr.length - 1; i >= 0; i--) {
        let temp = new ListNode(null);
        res.val = arr[i];
        temp.next = res;
        res = temp;
    }

    return res.next;
};

数组转链表和链表转数组这两种方法在链表中十分常用，大家可以去多看看，以备不时之需。

分治法

如果说上一种解法是简单，那么接下来这种解法就属于高级且有难度了 —— 分治法。它大致是这样的，它不像其他方法一样从第一个开始合并第二个并一直合并到最后一个，而是从中间开始不断分为左右两部分，对左右两部分进行合并排序。

整体思路如下：通过中间值将其分为左右两部分，然后分别调用写好的相关函数进行合并。第一次合并两个链表，第二次合并四个链表，不断合并新的两个链表，直到合并完所有的链表返回最终结果即可。对分治法不熟练的朋友看这思路会很吃力，所以尽量结合代码一起看。

相关代码如下：

var mergeKLists = function(lists) {
    if(!lists.length) return null;
    return mergeList(lists, 0, lists.length - 1);
};
function mergeList(lists, start, end) {
    if(start === end) {
        return lists[start];
    }
    const mid = start + ((end - start) >> 1);
    const leftList = mergeList(lists, start, mid);
    const rightList = mergeList(lists, mid + 1, end);
    return merge(leftList, rightList);
}
function merge(head1, head2) {
    let newHead = new ListNode(0), p = newHead;
    while(head1 && head2) {
        if(head1.val <= head2.val) {
            p.next = head1;
            head1 = head1.next;
        } else {
            p.next = head2;
            head2 = head2.next;
        }
        p = p.next;
    }
    p.next = head1 ? head1 : head2;
    return newHead.next;
}

合并二叉树

这是 617 题

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

解题思路

这是一道简单题，对这道题而言，本质上是一个遍历的问题。二叉树有三种遍历方式，前序遍历，中序遍历以及后序遍历。看到这题很显然是递归解法（二叉树的题目 90%以上都可以用递归解决）。接下来就来介绍用递归法来解决此题。

递归解法

对于二叉树来说，我们其实可以把这两个树想像成两个数组，这样就可以变成合并数组的题目了。然后继续简化，如果我们像遍历数组那样，依次遍历两个二叉树中的每个节点，再把它们进行相加，那问题就比较容易解决了。这里就相当于将数组 a 合并到数组 b 中，然后返回数组 b 即可

遍历二叉树很简单，这里使用前序遍历就可以了。遍历的过程中依次把访问到的节点值相加，因为题目没有说不能改变树的值和结构，所以我们不用再创建新的节点，直接可以将树 b 合并到树 a 后再返回就可以了。

相关代码如下：

var mergeTrees = function (root1, root2) {
    if (!root1 && !root2) {
        return null;
    }
    if (!root1) return root2;
    if (!root2) return root1;
    root1.val = root1.val + root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
};

通过递归更新将 root2 替换到 root1 上，和上述思路一样。如果还有没看明白的小伙伴，可以在纸上多画画图，说不定就能更清楚了。

二叉树的最大深度

这是力扣第 104 题

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明:  叶子节点是指没有子节点的节点。

解题思路

这是一道简单题，但是这道二叉树的题目不在于是否最后能做出来，在于能否能想清楚思路过程，这点是非常重要的。二叉树里最重要的思想就是递归思想，因此掌握二叉树的思想及其本质是我们做这道题目的关键。

对于这道题，我们要弄清楚一个东西，那就是根节点的高度就是二叉树的最大深度，因此此题我们可以转换成通过根节点高度来求二叉树的最大深度。

递归解法

使用递归的方法分为如下三步：

• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层逻辑

对于后序遍历的顺序是：左子树、右子树、根。因此先递归左子树的最大高度，然后递归右子树的最大高度，再来求根的最大高度。对于左子树和右子树来说，也都是同样的操作。另外对于如何终止二叉树的遍历的问题，当没有东西遍历了，就可以终止。确定好这些，代码就基本出来了。

相关代码如下：

var maxdepth = function(root) {
    const getdepth=function(node){
        if(node===null){
            return 0;
        }
        let leftdepth=getdepth(node.left);
        let rightdepth=getdepth(node.right);
        let depth=1+Math.max(leftdepth,rightdepth);
        return depth;
    }
    return getdepth(root);
};

简化代码解法

这一种 js 写法代码就非常简洁了，简化了相关代码，增强了可读性，也比较容易理解。但是和递归解法相比，可以多试试递归解法，毕竟二叉树就是递归思想。提到二叉树我们首先想到的也是递归。下面这种写法可以作为了解。

相关代码如下：

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