337. House Robber III

题干简述：

给我们一个二叉树的根节点，求该二叉树最大根节点和；需要注意的是，这其中的节点不可相邻。

解题思路

首先，由于是二叉树的题目，我们还是先从递归的方向来思考。正如我上一篇文章 687. Longest Univalue Path 说的，递归函数重要的有四点：

  • 输入参数：我们传递什么进去；
  • 输出结果：我们返回什么出来给上一层使用；
  • 函数的功能/目的：这个递归函数是为了解决什么问题；
  • 终止条件：当输入参数满足什么结果时，代表我们已经执行到最底层，需要停止递归并开始逐层返回；

代入到这一题，输入参数与终止条件自不用提，我们需要将注意力放在输出结果与函数的功能与目的上。正如题干所描述的，其中的节点不可相邻。此时，如果我们传入一个节点 node 进入递归函数，在计算的时候，我们就需要考虑，需不需要使用这个节点：如果不使用这个节点，那么求和的时候，用的就是这个节点的父节点与其左右子树的和；如果使用这个节点，那求和的时候使用的就是这个节点的值，与其子节点的子树的结果之和。无论哪一种情况，我们返回给上一层的都是当前节点对应树的最大和，至于怎么用那就是上层节点的事情了，先放一边。据此，我们可以先得出代码如下：

var rob = function(root) {
    if (!root) return 0;
    let money = root.val;
    if (root.left) {
        money += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        money += rob(root.right.left) + rob(root.right.right);
    }
    return Math.max(money, rob(root.left) + rob(root.right));
};

大功告成，我自信的跑了下题目提供的几个用例，完美通过，自信提交，然而，却提示错误：

337-1

实际上，我们的算法并没有问题，问题在于它的性能。性能问题出现的原因在于，每次我们计算节点的时候，都会出现重复计算的情况。当前root.right.left 对应的节点，在 计算 root.right的时候又会计算一次，这个是则 root.left。这其实就是我们之前遇到过的动态规划的问题，斐波那契数列解决的方法是通过数组进行缓存，二叉树的数据结构并不适合用数组来缓存，我们可以使用 map 结构来缓存，需要使用的时候，先判断 map 中是否存在，已缓存则使用缓存的数据，未缓存则重新计算，代码如下：

const cache = new Map();
var rob = function(root) {
    if (!root) return 0;
    if (cache.has(root)) return cache.get(root);
    let money = root.val;
    if (root.left) {
        money += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        money += rob(root.right.left) + rob(root.right.right);
    }
    const res = Math.max(money, rob(root.left) + rob(root.right))
    cache.set(root, res);
    return res;
};

提交后结果如下, see, 肉眼可见的性能提升:

337-2

当然，我们还可以进一步优化。实际上，我们上面刚刚提到动态规划，但是我们刚刚改写的代码并没有用到动态规划的知识，只是用了动态规划的一种优化方法。这一题，动态规划也同样适用。

动态规划简单来说，主要用来解决最优解问题，这一题，可以分为两种情况，分别是包含当前根节点与不包含当前根节点。我们的最终结果，就是这两种情况的最大值，即最优解。按动态规划的解法，我们需要有一个二维数组，用于存储各个节点的两种情况下的最优解，但是由于二叉树的数据结构，这里我们依旧使用 map 结构进行存储。包含当前根节点时，最优解必然是 root.val + rob(root.left.left)+ rob(root.left.right) + rob(root.right.left)+ rob(root.right.right), 由于我们依旧通过 map 结构存储了，也就可以替换成root.val + map(root.left) + map(root.right)，思路还是一样。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dpMap = new Map();
    
    const dp = (node) => {
        if (!node) return [0,0];
        
        const left = dp(node.left);
        const right = dp(node.right);
        
        if(!dpMap.has(node)) {
            dpMap.set(node, [0,0])
        }
        
        const res = dpMap.get(node);
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 存放不包括当前节点情况，此时去的是其左右子树包含自身与不包含自身的最大值之和，因为此时无论子树如何都是有效的；
        res[1] = node.val + left[0] + right[0]; // 存放包括当前节点情况,此时加的值为其左右子树不包含自身的情况最大值；
        
        return res;
    };
    
    const result = dp(root)
    
    return Math.max(result[0], result[1]);
};

这里如果要进一步优化的话，我们可以从空间复杂度来考虑。每次递归返回到上一层时，上一层节点实际上只用到了自己的两个子树的相关值，因此我们也没有必要把每个节点的两种情况的值都存起来，这两个值直接通过函数返回给上一层就可以了，这也是递归函数带来的便利之一。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dp = (node) => {
        if (!node) return [0,0];
        
        const left = dp(node.left);
        const right = dp(node.right);
        
        const unincludeNode = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 存放不包括当前节点情况，此时去的是其左右子树包含自身与不包含自身的最大值之和，因为此时无论子树如何都是有效的；
        const includeNode = node.val + left[0] + right[0]; // 存放包括当前节点情况,此时加的值为其左右子树不包含自身的情况最大值；
        
        return [unincludeNode, includeNode];
    };
    
    const result = dp(root)
    
    return Math.max(result[0], result[1]);
};

最终结果如下：

337-3

Q.E.D.

Take it easy