【牛客NC178】 打家劫舍(三) JAVA全过程详解

　　你是一个经验丰富的小偷，经过上次在街边和湖边得手后你准备挑战一次自己，你发现了一个结构如二叉树的小区，小区内每个房间都存有一定现金。你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。
问：给定一个二叉树结构的小区，你无法在不触动警报的情况下同时偷窃两个相邻的房间，请在不触动警报的情况下最多的偷窃金额。

输入： 给出一个如下图所示的二叉树

 

分析： 偷窃第 1 层可获得 2 ，偷窃第 2 层可获得 1+2 = 3 ，偷窃第 3 层可获得 2+1=3 ，因此偷窃第 1 层+第 2 层 = 5 是最优方案

输出： 5

输入： 给出一个如下图所示的二叉树

分析： 偷窃第 1 层可获得 3，偷窃第 2 层可获得 2+10 = 12 ，因此偷窃第2层 = 12 是最优方案

输出： 12

　　该问题是一个典型的动态规划问题，我们首先要弄明白题干中所说的“不能同时偷窃两个相邻的房间”的含义。比如对于当前节点nowNode，与它相邻的节点只有两种，一种是向上寻找nowNode的父节点（可能会有1个），另一种是向下寻找nowNode的子节点（可能会有2个），除此之外再没有与nowNode相邻的结点。因此，nowNode与它的“孙子”节点是不相邻的、与它的“爷爷”结点也是不相邻、与其他节点更是毫无关系，完全不影响同时对它们进行偷窃。

　　明白上述概念以后，该题很容易了。我们想计算从nowNode开始能偷窃的最大价值V( nowNode )，那么对nowNode就只有2种选择：(1)偷窃nowNode，不能再偷窃它的2个“儿子”，但可以偷窃它的4个“孙子”；(2)不偷窃nowNode和它的4个“孙子”，但可以偷窃它的2个“儿子”。只需要比较这两种情况带来的收益大小，更大的那种方案就是我们要求的V( nowNode )，由此我们获得了V()的表达式如下

V( nowNode ) = max {  nowNode本身的价值+V( nowNode的“孙子”们 ) ， V( nowNode的“儿子”们 )  }

　　实现一个函数giveValue( TreeNode root )完成计算价值的任务。不难想到，只有把root子孙们的最大价值计算完，才能计算root自己的最大价值，因此giveValue函数使用后序遍历的大框架

private void giveValue( TreeNode root ) {
        if ( root == null )
            return;
        giveValue(root.left);
        giveValue(root.right);

        // ********************
        // 计算root自己的价值
        // ********************

    }

　　接下来是计算root自己的最大价值。

　　首先定义int变量erValue存储2个“儿子”的最大价值之和、sunValue存储4个“孙子”的最大价值之和，初始值均为0。如果root有左孩子，就将左孩子的val加给erValue，如果左孩子也有左孩子/右孩子（也即root的“孙子”）就把它们的val加给sunValue。同理，如果root有右孩子，就将右孩子的val加给erValue，如果右孩子也有左孩子/右孩子（也即root的“孙子”）就把它们的val加给sunValue。

　　经过这样几次判断计算，就求出了“儿子”和“孙子”的最大价值和，只需要取 root.val + sunValue 和 erValue 的最大值即可，由此我们得到了完整的giveValue函数。

    private void giveValue( TreeNode root ) {
        if ( root == null )
            return;
        giveValue(root.left);
        giveValue(root.right);

        int erValue = 0;    // 2个儿子的最大value
        int sunValue = 0;   // 4个孙子的最大value
        if (root.left != null) {
            erValue  += root.left.val;
            sunValue += root.left.left  == null ? 0 : root.left.left.val;
            sunValue += root.left.right == null ? 0 : root.left.right.val;
        }
        if (root.right != null) {
            erValue  += root.right.val;
            sunValue += root.right.left  == null ? 0 : root.right.left.val;
            sunValue += root.right.right == null ? 0 : root.right.right.val;
        }
        root.val = Math.max( root.val + sunValue , erValue );
    }

　　对根结点root调用一次giveValue，再直接返回root.val就是从root开始能偷窃的整体最大价值。

    public int rob(TreeNode root) {
        giveValue(root);
        return root.val;
    }

　　笔者的完整源代码如下，可以直接提交通过该题。该代码仅供大家参考，如各位朋友有更好的想法欢迎留言讨论，期待与您共同进步！

import java.util.*;

public class Solution {
    public int rob(TreeNode root) {
        giveValue(root);
        return root.val;
    }

    private void giveValue(TreeNode root) {
        if (root == null) return;
        giveValue(root.left);
        giveValue(root.right);

        int erValue = 0;    // 2个儿子的value
        int sunValue = 0;   // 4个孙子的value
        if (root.left != null) {
            erValue += root.left.val;
            sunValue += root.left.left == null ? 0 : root.left.left.val;
            sunValue += root.left.right == null ? 0 : root.left.right.val;
        }
        if (root.right != null) {
            erValue += root.right.val;
            sunValue += root.right.left == null ? 0 : root.right.left.val;
            sunValue += root.right.right == null ? 0 : root.right.right.val;
        }
        root.val = Math.max(root.val + sunValue, erValue);
        return;
    }
}