专栏首页mathorLeetCode337. 打家劫舍 III

LeetCode337. 打家劫舍 III

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public Map<TreeNode,Integer> trueCache = new HashMap<TreeNode,Integer>();
    public Map<TreeNode,Integer> falseCache = new HashMap<TreeNode,Integer>();
    public int dfs(TreeNode root,boolean canRob) {
        if(root == null)
            return 0;
        if(canRob && trueCache.containsKey(root))
            return trueCache.get(root);
        if(!canRob && falseCache.containsKey(root))
            return falseCache.get(root);
        int ans = 0;
        if(canRob)
            ans = Math.max(ans,
                           root.val + dfs(root.left,false) + dfs(root.right,false));
        ans = Math.max(ans,
                       dfs(root.left,true) + dfs(root.right,true));
        if(canRob) 
            trueCache.put(root,ans);
        if(!canRob) 
            falseCache.put(root,ans);
        return ans;
    }
    public int rob(TreeNode root) {
        return dfs(root,true);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

     后序遍历的非递归代码得说一下,首先后序遍历得顺序是左右中,我们知道先序遍历的压栈顺序是先压右再压左,这样出来的顺序就是中左右,如果把先序遍历的压栈顺序稍微变一...

    mathor
  • Socket

    mathor
  • LeetCode69. x 的平方根

     这道题直接一个return Math.sqrt就出来了,但是秉承着学习的心态,尝试着用二分法ac  首先要确定的就是左右区间,左区间是0无疑了,那么右...

    mathor
  • LeetCode 二叉树系统题解

    TIPS:前中后序遍历区别在于三字中的中间那个字,前、中、后序分别对应左、根、右。

    Yano_nankai
  • 5330. 分裂二叉树的最大乘积(dfs)

    题目链接:https://leetcode-cn.com/contest/weekly-contest-174/problems/maximum-product...

    Ch_Zaqdt
  • 画解算法:111. 二叉树的最小深度

    https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

    灵魂画师牧码
  • LeetCode 114. Flatten Binary Tree to Linked List

    Given a binary tree, flatten it to a linked list in-place.

    ShenduCC
  • linux每日命令(26):Linux文件属性详解

    Linux 文件或目录的属性主要包括:文件或目录的节点、种类、权限模式、链接数量、所归属的用户和用户组、最近访问或修改的时间等内容。具体情况如下:

    用户1214487
  • 使用cell ranger进行单细胞转录组定量分析

    在RNA_seq数据的定量分析中,都是首先将reads比对到参考基因组,然后再使用定量软件进行定量,比如经典的hisat+stringTie的分析策略,对于单细...

    生信修炼手册
  • 验证二叉搜索树

    大忽悠爱学习

扫码关注云+社区

领取腾讯云代金券