https://leetcode.cn/problems/house-robber-iii/description/
此前做过此题,不过时隔一年再做一遍有新的理解
class Solution {private Map<TreeNode,Integer> vis = new HashMap<>();public int rob(TreeNode root) {// 在二叉树上做选择,不能选择直接相连的节点// f[i] 表示以 i 为根的树中能获取到的最大金额,集合法表示以i为根的树中的所有可能的走法,属性为最大价值// 从子树考虑一直推导到根节点// 以节点i是否偷取作为标准,也可划分子集// 偷i: 那么i的子节点都不能偷,只能偷i的孙子节点,节点编号为i/2/2=i/4// f[i]=max(f[i/4],f[i/4+1],f[i/4+2],f[i/4+3]) + nums[i],i/4>=0// 不偷i: 那么i1的子节点可以偷, f[i] = f[i/2]+f[i/2+1]//// 转化成树形dp做法:使用搜索dfs或者bfs,dfs递归需要定义函数意义// dfs(root)表示以root为根的树能获取到的最大金额// 不偷: dfs(root) = dfs(root.left) + dfs(root.right)// 偷 dfs(root) = root.val + dfs(root.left.left) + dfs(root.left.right) + dfs(root.right.left) + dfs(root.right.right)// 边界条件: if(root==null), return 0,为叶子结点时返回值// 无左右儿子,直接返回当前节点值return dfs(root);}int dfs(TreeNode root) {// 后续遍历if (root == null) return 0;if (root.left == null && root.right == null) return root.val;// 剪枝if (vis.get(root) != null) return vis.get(root);// 不偷rootint left = dfs(root.left);int right = dfs(root.right);// 偷rootint steal=root.val;if (root.left != null) {steal += dfs(root.left.left) + dfs(root.left.right);}if (root.right != null) {steal += dfs(root.right.left) + dfs(root.right.right);}int res = Math.max(left+right, steal);// 运行到此处时,意味着当前节点结果计算完毕,可以保存已计算的结果进行剪枝vis.put(root,res);return res;}
}