LeetCode-337 House Robber III

题目描述

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

题目大意

给定一棵二叉树，不能同时选择相邻结点的数值，求可能得到的结点值之和的最大值。

示例

Input: [3,2,3,null,3,null,1]

     3
    / 
   2   3
        
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Input: [3,4,5,1,3,null,1]

     3
    / 
   4   5
  /     
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

解题思路

递归遍历，计算当前结点以及其孙子结点的数值之和，和该结点的两个孩子结点之和进行比较，返回较大值。

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        int l = 0, r = 0;
        
        return dfs(root, l, r);
    }
    
    int dfs(TreeNode* root, int& l, int& r) {
        if(root == NULL)
            return 0;
        
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = dfs(root->left, ll, lr);
        r = dfs(root->right, rl, rr);
        
        return max(root->val + ll + lr + rl + rr, l + r);
    }
};