337. House Robber III
Tags:
Medium
Skills:
TreeDP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tính số tiền tối đa mà kẻ trộm có thể lấy từ các ngôi nhà được biểu diễn dưới dạng cây nhị phân. Điều kiện là không được trộm hai ngôi nhà kề nhau (liên kết trực tiếp). Đây là một bài toán điển hình sử dụng quy hoạch động kết hợp với duyệt cây (DFS).
Approach
Công thức
Time and space complexity
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function rob(root: TreeNode | null): number {
16 function dfs(node: TreeNode | null): [number, number] {
17 if (!node) return [0, 0]
18 const [rob_left, not_rob_left] = dfs(node.left)
19 const [rob_right, not_rob_right] = dfs(node.right);
20
21 const rob_current = node.val + not_rob_left + not_rob_right;
22 const not_rob_current = Math.max(rob_left, not_rob_left) + Math.max(rob_right, not_rob_right);
23 return [rob_current, not_rob_current]
24 }
25
26 const [rob_root, not_rob_root] = dfs(root);
27 return Math.max(rob_root, not_rob_root)
28};