LeetCode刷题笔记——T0337 打家劫舍Ⅲ

题目描述：

题目思路：

本题属于动态规划题目，即遍历二叉树，获得偷窃最大值。二叉树的遍历可以分为：深度优先遍历，前序/中序/后序遍历；广度优先遍历，层序遍历。本体需要使用后序遍历方式，当前结点投不投在乎与，其左右孩子所掌握的金额值不值得偷当前结点。题目中使用得dp数组大小为2，dp[0]表示当前结点不偷时，返回得最大金额，dp[1]表示当前结点被偷时，返回的最大金额。根据左右孩子是否被偷，再来查看当前结点偷与不偷。

代码如下：

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

        TreeNode(int v = 0, TreeNode* l = nullptr, TreeNode* r = nullptr) :val(v), left(l), right(r) {}
    };

    class Solution {
    public:
        int rob(TreeNode* root) {
            vector<int> res = robTree(root);
            return max(res[0], res[1]);
        }
        vector<int> robTree(TreeNode* cur) {
            if (cur == nullptr) return vector<int>{0, 0};
            vector<int> left = robTree(cur->left);
            vector<int> right = robTree(cur->right);
            int val1 = max(left[0], left[1]) + max(right[0], right[1]);
            int val2 = cur->val + left[0] + right[0];
            return vector<int>{val1, val2};
        }
    };

提交结果：

本题题解思路来源于：代码随想录