My exponential solution got TLE, anyone can hint a dp solution?

• ``````public int RobIII(TreeNode root)
{
if (root == null) return 0;
int max  = Math.Max(RobIII(root, true), RobIII(root, false));
return max;
}

private int RobIII(TreeNode root, bool canrob)
{
if (root == null) return 0;
if (canrob)
{
return Math.Max(RobIII(root.left, false) + RobIII(root.right, false) + root.val, RobIII(root.left, true) + RobIII(root.right, true) );

}
else {
return RobIII(root.left, true) + RobIII(root.right, true);

}
}``````

• I came up with this bottom-up O(n) solution but the mock interview ended :(

``````public int RobIII(TreeNode root)
{
int[] result = HelperRobIII(root);
return Math.Max(result[0], result[1]);
}

private int[] HelperRobIII(TreeNode root)
{ // int[]{sum, robbed}
if (root == null) return null;
int[] left = HelperRobIII(root.left);
int[] right = HelperRobIII(root.right);
if (left == null && right == null) return new int[] { root.val, 0 };
else if (left != null && right == null) {
int max = Math.Max(root.val + left[1], left[0]);
return new int[] { max, left[0] };
}
else if (right != null && left == null)
{
int max = Math.Max(root.val + right[1], right[0]);
return new int[] { max, right[0] };
}
else {
int max = Math.Max(left[0] + right[0], root.val + left[1] + right[1]);
return new int[] { max, left[0] + right[0] };
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.