欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

House Robber III

程序员文章站 2022-07-12 12:30:35
...

House Robber III

1. 解析 

题目大意,求解二叉树所有非相邻节点和的最大值。题目还是很难的,就是会给人一种有思路,但就是写不出来的感觉,要求对递归理解非常透彻才有可能设计出来。

2. 分析

参考@Grandyang的解法,主要分成两种情况考虑:

①考虑根节点的值,不考虑左右子树的根节点

②不考虑根节点的值,考虑左右子树的根节点

综上,为了不重复的检索,我们可以借助hashtable存储检索过的节点,用带有记忆功能的递归,每一次递归返回①②情况的最大值即可。虽然思路看起来蛮简单的,但中间的递归过程还是蛮复杂的,有空我也要自己动手去探索一下过程~~~

/**
 * 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) {
        map<TreeNode*, int> exist;     
        return DFS(root, exist);
    }
    int DFS(TreeNode* root, map<TreeNode*, int>& exist){
        if (!root) return 0;
        if (exist[root]) return exist[root];
        int val = 0;
        if (root->left){ //只包含
            val += DFS(root->left->left, exist) + DFS(root->left->right, exist);       
        }
        if (root->right){
            val += DFS(root->right->left, exist) + DFS(root->right->right, exist);          
        }
        val = max(DFS(root->left, exist) + DFS(root->right, exist), root->val + val);
        exist[root] = val;
        return val;
    }
};

 第二种解法思路差不多,将上面的两个过程值保存在vector数组当中,即res[0]代表上面的第①种情况,res[1]代表第②种情况。

/**
 * 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){
        vector<int> res = DFS(root);
        return max(res[0], res[1]);
    }
    vector<int> DFS(TreeNode* root){
        if (! root) return vector<int>(2, 0);
        vector<int> left = DFS(root->left);
        vector<int> right = DFS(root->right);
        vector<int> res(2, 0);
        res[0] = max(left[0], left[1]) + max(right[0], right[1]);
        res[1] = root->val + left[0] + right[0];
        return res;
    }
};

 3. 类似的题目

House Robber II

Convert Sorted List to Binary Search Tree

Unique Binary Search Trees II

[1]https://www.cnblogs.com/grandyang/p/5275096.html