LeetCode337打家劫舍III

Posted on | | Visitors:
Words count in article: 260 字 | Reading time ≈ 1 分

题目链接

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

题解

  • 递归写法
  • 这个思路似乎是错的(不过我提交后是在某一个测试用例是超时了)，先把这份代码放这儿吧，后边补正确的解法
    • 题目要求两个结点不能相连，这不等于隔层求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Problem: LeetCode 337
// URL: https://leetcode-cn.com/problems/house-robber-iii/
// Tags: Tree DFS Recursion
// Difficulty: Medium

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
public:
    int rob(TreeNode* root) {
        // 空结点，结果为0
        if(root==nullptr)
            return 0;
        // 抢当前结点及其隔层
        int result1 = root->val;
        if(root->left!=nullptr)
            result1 += rob(root->left->left) + rob(root->left->right);
        if(root->right!=nullptr)
            result1 += rob(root->right->left) + rob(root->right->right);
        // 抢根结点下一层的两个结点及其隔层
        int result2 = rob(root->left) + rob(root->right);

        return max(result1, result2);
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!