LeetCode: House Robber III

https://leetcode.com/problems/house-robber-iii/, problem statement:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Key idea is to do a DFS (Depth-First-Search) but using post-order traversal (left-right-current). Whenever the current node can be robbed, it will be robbed, but regardless we also need to try with the current node not being robbed (think about an extrapolated tree such as 1000->1(R)->1(R)->1000(R). In this case the best solution is 2000). We should also try from the beginning the root being robable and with it being not robable. This solution will be exponential and will eventually time out for long inputs. An DP (Dynamic Programming) like approach comes handy here: keep a hash table with the results seen for the current node and the current rob state, and whenever you see that situation, pull the result out of the hash table. This will speed up the code significantly, or at least enough to be accepted. Cheeers, Marcelo.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode tree = new TreeNode(3);
            tree.left = new TreeNode(2);
            tree.right = new TreeNode(3);
            tree.left.right = new TreeNode(3);
            tree.right.right = new TreeNode(1);

            Solution sol = new Solution();
            Console.WriteLine(sol.Rob(tree));
        }
    }
     public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
     }

    public class Solution
    {
        public int Rob(TreeNode root)
        {
            if (root == null) return 0;

            int maxAmount = Int32.MinValue;
            Hashtable htMap = new Hashtable();
            MaxRob(root, true, htMap, ref maxAmount);
            MaxRob(root, false, htMap, ref maxAmount);

            return maxAmount;
        }

        private void MaxRob(TreeNode currentNode,
                            bool canRob,
                            Hashtable htMap,
                            ref int maxAmount)
        {
            if (currentNode == null)
            {
                return;
            }

            string key = currentNode.GetHashCode().ToString() + "@" + canRob.ToString();
            if (htMap.ContainsKey(key))
            {
                maxAmount = (int)htMap[key];
                return;
            }

            int maxAmountLeft = 0;
            int maxAmountRight = 0;

            if (canRob)
            {
                //Will rob current
                MaxRob(currentNode.left, false, htMap, ref maxAmountLeft);
                MaxRob(currentNode.right, false, htMap, ref maxAmountRight);

                if (maxAmountLeft + maxAmountRight + currentNode.val > maxAmount)
                {
                    maxAmount = maxAmountLeft + maxAmountRight + currentNode.val;
                }
            }

            //Skip current
            maxAmountLeft = 0;
            maxAmountRight = 0;
            MaxRob(currentNode.left, true, htMap, ref maxAmountLeft);
            MaxRob(currentNode.right, true, htMap, ref maxAmountRight);

            if (maxAmountLeft + maxAmountRight > maxAmount)
            {
                maxAmount = maxAmountLeft + maxAmountRight;
            }

            if (!htMap.ContainsKey(key))
            {
                htMap.Add(key, maxAmount);
            }
        }
    }
}