leetcode-house-robber-iii

题目大意

　　https://leetcode.com/problems/house-robber-iii/

　　一个强盗可以对一棵树上从根节点至下对每个节点进行rob，要求相邻两个节点不能rob。

题目分析

　　这个题接续house robber i和house robber ii。但更为复杂的是，这次是一棵树，实质上还是进行先搜索，再进行记忆化，搜索就是基于穷举法，每次遇到一个节点，选择是留还是弃。留的话，那么下次的搜索只能从当前结点的儿子节点的儿子节点开始搜索。弃的话，下次搜索的起点是儿子节点。在此基础上，加上记录，但这次记录的不是数字了，而是TreeNode节点，可以利用Map<TreeNode, Integer>存储。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Map<TreeNode, Integer> cache;
    private int search(TreeNode cur) {
        if(cur == null) {
            return 0;
        }
        if(cache.containsKey(cur)) {
            return cache.get(cur);
        }
        //留当前结点
        int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
        if(cur.left != null) {
            v1 = search(cur.left.left);
            v2 = search(cur.left.right);
        }
        if(cur.right != null) {
            v3 = search(cur.right.left);
            v4 = search(cur.right.right);
        }
        int max = cur.val + v1 + v2 + v3 + v4;
        //弃当前结点
        int v5 = 0, v6 = 0;
        v5 = search(cur.left);
        v6 = search(cur.right);
        max = Math.max(max, v5 + v6);
        cache.put(cur, new Integer(max));
        return max;
    }
    
    public int rob(TreeNode root) {
        cache = new HashMap<TreeNode, Integer>();
        return search(root);
    }
}

　　时间复杂度就是树的节点数。