Approach: Post-order DP returning (rob-this, skip-this)

def rob(self, root):
    def dfs(node):
        if not node: return (0, 0)
        l = dfs(node.left); r = dfs(node.right)
        take = node.val + l[1] + r[1]
        skip = max(l) + max(r)
        return (take, skip)
    return max(dfs(root))

Complexity: O(n) time, O(h) space.

Full Solution — all languages

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):
        def dfs(node):
            if not node: return (0, 0)
            l = dfs(node.left); r = dfs(node.right)
            take = node.val + l[1] + r[1]
            skip = max(l) + max(r)
            return (take, skip)
        return max(dfs(root))

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left), r = dfs(node.right);
        int take = node.val + l[1] + r[1];
        int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{take, skip};
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int rob(TreeNode* root) {
        function<pair<int,int>(TreeNode*)> dfs = [&](TreeNode* node) -> pair<int,int> {
            if (!node) return {
                0, 0
            };
            auto l = dfs(node->left);
            auto r = dfs(node->right);
            int take = node->val + l.second + r.second;
            int skip = max(l.first, l.second) + max(r.first, r.second);
            return {
                take, skip
            };
        };
        auto res = dfs(root);
        return max(res.first, res.second);
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {number}
 */ var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        const l = dfs(node.left), r = dfs(node.right);
        const take = node.val + l[1] + r[1];
        const skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return [take, skip];
    };
    const res = dfs(root);
    return Math.max(res[0], res[1]);
};

House Robber III

Example 1

Example 2

Constraints