337.打家劫舍III

链接：337.打家劫舍III
难度：Medium
标签：树、深度优先搜索、动态规划、二叉树
简介：计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

题解 1 - typescript

• 编辑时间：2020-08-05
• 执行用时：108ms
• 内存消耗：44MB
• 编程语言：typescript
• 解法介绍：深度优先搜索，对每个节点进行判断偷与不偷的情况。

function rob(root: TreeNode | null): number {
  const f = new Map<TreeNode | null, number>();
  const g = new Map<TreeNode | null, number>();
  f.set(null, 0);
  g.set(null, 0);
  dfs(root);
  return Math.max(f.get(root)!, g.get(root)!);
  function dfs(node: TreeNode | null) {
    if (node === null) return;
    dfs(node.left);
    dfs(node.right);
    f.set(node, node.val + g.get(node.left)! + g.get(node.right)!);
    g.set(
      node,
      Math.max(f.get(node.left)!, g.get(node.left)!) +
        Math.max(f.get(node.right)!, g.get(node.right)!)
    );
  }
}

题解 2 - cpp

• 编辑时间：2023-09-18
• 执行用时：28ms
• 内存消耗：30.57MB
• 编程语言：cpp
• 解法介绍：dfs时记录偷取当前节点和不偷取时的最大值。

class Solution {
public:
    vector<int> find(TreeNode *node) {
        vector<int> res{0, 0};
        if (node) {
            auto l = find(node->left), r = find(node->right);
            res[0] = max(l[0], l[1]) + max(r[0], r[1]);
            res[1] = l[0] + r[0] + node->val;
        }
        return res;
    }
    int rob(TreeNode* root) {
        auto res = find(root);
        return max(res[0], res[1]);
    }
};

题解 3 - python

• 编辑时间：2023-09-18
• 执行用时：52ms
• 内存消耗：18.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def find(node: Optional[TreeNode]) -> List[int]:
            res = [0, 0]
            if node:
                l, r = find(node.left), find(node.right)
                res[0] = max(l) + max(r)
                res[1] = l[0] + r[0] + node.val
            return res
        return max(find(root))

题解 4 - rust

• 编辑时间：2023-09-18
• 执行用时：4ms
• 内存消耗：2.81MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
fn find(node: Option<&Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![0, 0];
    if let Some(node) = node {
        let node_ref = node.as_ref().borrow();
        let l = find(node_ref.left.as_ref());
        let r = find(node_ref.right.as_ref());
        res[1] = l[0] + r[0] + node_ref.val;
        res[0] = l.into_iter().max().unwrap() + r.into_iter().max().unwrap();
    }
    res
}
impl Solution {
    pub fn rob(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let node = root.as_ref();
        find(root.as_ref()).into_iter().max().unwrap()
    }
}