LeetCode 337: House Robber III (Tree DP with Rob/Skip States)
LeetCode 337Binary TreeDynamic ProgrammingToday we solve LeetCode 337 - House Robber III.
Source: https://leetcode.com/problems/house-robber-iii/
English
Problem Summary
Each tree node is a house with money. If we rob a node, we cannot rob its direct children. Return the maximum money we can rob from the whole tree.
Key Insight
For every node, compute two states:
- rob: best value if we rob this node.
- skip: best value if we do not rob this node.
If we rob current, both children must be skipped. If we skip current, each child can choose its better state independently.
State Transition
Let left = (leftRob, leftSkip), right = (rightRob, rightSkip):
rob = node.val + leftSkip + rightSkip
skip = max(leftRob, leftSkip) + max(rightRob, rightSkip)
Answer for root is max(rootRob, rootSkip).
Complexity Analysis
Time: O(n), each node is processed once.
Space: O(h) recursion stack, where h is tree height.
Common Pitfalls
- Trying to greedily rob larger-valued nodes first (local choice fails globally).
- Forgetting that left and right child decisions are independent when parent is skipped.
- Returning only one state from DFS instead of both rob/skip.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root); // [rob, skip]
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int rob = node.val + left[1] + right[1];
int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{rob, skip};
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
robCur, skipCur := dfs(root)
if robCur > skipCur {
return robCur
}
return skipCur
}
func dfs(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
leftRob, leftSkip := dfs(node.Left)
rightRob, rightSkip := dfs(node.Right)
robCur := node.Val + leftSkip + rightSkip
skipCur := max(leftRob, leftSkip) + max(rightRob, rightSkip)
return robCur, skipCur
}
func max(a, b int) int {
if a > b {
return a
}
return b
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
auto [take, skip] = dfs(root);
return max(take, skip);
}
pair dfs(TreeNode* node) {
if (!node) return {0, 0};
auto [lTake, lSkip] = dfs(node->left);
auto [rTake, rSkip] = dfs(node->right);
int take = node->val + lSkip + rSkip;
int skip = max(lTake, lSkip) + max(rTake, rSkip);
return {take, skip};
}
}; # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root):
take, skip = self.dfs(root)
return max(take, skip)
def dfs(self, node):
if not node:
return 0, 0
l_take, l_skip = self.dfs(node.left)
r_take, r_skip = self.dfs(node.right)
take = node.val + l_skip + r_skip
skip = max(l_take, l_skip) + max(r_take, r_skip)
return take, skip/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
const [take, skip] = dfs(root);
return Math.max(take, skip);
};
function dfs(node) {
if (!node) return [0, 0];
const [lTake, lSkip] = dfs(node.left);
const [rTake, rSkip] = dfs(node.right);
const take = node.val + lSkip + rSkip;
const skip = Math.max(lTake, lSkip) + Math.max(rTake, rSkip);
return [take, skip];
}中文
题目概述
每个二叉树节点代表一间房子，若偷了某个节点，就不能偷它的直接子节点。求整棵树可偷到的最大金额。
核心思路
对每个节点维护两个状态：
- rob：偷当前节点时的最优值。
- skip：不偷当前节点时的最优值。
偷当前节点时，左右孩子都只能走 skip；不偷当前节点时，左右孩子各自取更优状态即可。
状态转移
设左子树状态为 (leftRob, leftSkip)，右子树状态为 (rightRob, rightSkip)：
rob = node.val + leftSkip + rightSkip
skip = max(leftRob, leftSkip) + max(rightRob, rightSkip)
根节点答案是 max(rootRob, rootSkip)。
复杂度分析
时间复杂度：O(n)，每个节点只访问一次。
空间复杂度：O(h)，递归栈高度为树高。
常见陷阱
- 按节点值贪心选择，忽略树结构约束。
- 父节点不偷时，错误地把左右孩子绑定成同一种选择。
- DFS 只返回一个值，导致转移信息不足。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root); // [rob, skip]
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int rob = node.val + left[1] + right[1];
int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{rob, skip};
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
robCur, skipCur := dfs(root)
if robCur > skipCur {
return robCur
}
return skipCur
}
func dfs(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
leftRob, leftSkip := dfs(node.Left)
rightRob, rightSkip := dfs(node.Right)
robCur := node.Val + leftSkip + rightSkip
skipCur := max(leftRob, leftSkip) + max(rightRob, rightSkip)
return robCur, skipCur
}
func max(a, b int) int {
if a > b {
return a
}
return b
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
auto [take, skip] = dfs(root);
return max(take, skip);
}
pair dfs(TreeNode* node) {
if (!node) return {0, 0};
auto [lTake, lSkip] = dfs(node->left);
auto [rTake, rSkip] = dfs(node->right);
int take = node->val + lSkip + rSkip;
int skip = max(lTake, lSkip) + max(rTake, rSkip);
return {take, skip};
}
}; # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root):
take, skip = self.dfs(root)
return max(take, skip)
def dfs(self, node):
if not node:
return 0, 0
l_take, l_skip = self.dfs(node.left)
r_take, r_skip = self.dfs(node.right)
take = node.val + l_skip + r_skip
skip = max(l_take, l_skip) + max(r_take, r_skip)
return take, skip/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
const [take, skip] = dfs(root);
return Math.max(take, skip);
};
function dfs(node) {
if (!node) return [0, 0];
const [lTake, lSkip] = dfs(node.left);
const [rTake, rSkip] = dfs(node.right);
const take = node.val + lSkip + rSkip;
const skip = Math.max(lTake, lSkip) + Math.max(rTake, rSkip);
return [take, skip];
}
Comments