题目
337. 打家劫舍 III
我的思路
比较明显的动态规划
后序遍历:
当前节点作为根节点的最大和 = 左子树
maxSum(root) = max{maxSum(root.left)+maxSum(root.left),root.val+maxSum(root.left.left)...}
使用递归?空间复杂度3logn,时间复杂度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: vector<int> PostSearchRob(TreeNode *root) { if(root==NULL) { //vector<int> zeros(3,0); return vector<int>(3,0); } vector<int> leftVals = PostSearchRob(root->left); vector<int> rightVals = PostSearchRob(root->right); vector<int> myVals(3); myVals[1] = leftVals[0]; myVals[2] = rightVals[0]; myVals[0] = max(myVals[1]+myVals[2],root->val+leftVals[1]+leftVals[2]+rightVals[1]+rightVals[2]); return myVals; } int rob(TreeNode* root) { vector<int> robResults = PostSearchRob(root); return max(robResults[0],robResults[1]+robResults[2]); } }; /* 比较明显的动态规划 后序遍历: 当前节点作为根节点的最大和 = 左子树 maxSum(root) = max{maxSum(root.left)+maxSum(root.left),root.val+maxSum(root.left.left)...} 使用递归?空间复杂度3logn, */
拓展学习
官方题解中用哈希表存储