LeetCode: House Robber III C# https://leetcode.com/problems/house-robber-iii/

Please review for performance


  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.
  
  
  
  Gilad's comment: In simple words - you can't take the sum of parent and child. they have to be no directly connected nodes.  for example Max(level 1 +3, level 2)
  
  
  
  Example 1:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

  
  Output: 7 
  
  Explanation: Maximum amount of money the thief can rob = 3
  + 3 + 1 = 7. 
  
  Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

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


using System;
using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/problems/house-robber-iii/
    /// &lt;/summary&gt;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */

    [TestClass]
    public class HouseRobber3
    {
        [TestMethod]
        public void TestMethod1()
        {

            //     3              // level 1
            //    / \
            //    2   3           // level 2
            //    \   \
            //     3   1          // level 3
            TreeNode root = new TreeNode(3);
            root.left = new TreeNode(2);
            root.left.right = new TreeNode(3);
            root.right = new TreeNode(3);
            root.right.right = new TreeNode(1);
            //Output: 7
            //Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
            HouseRobber3Class robber = new HouseRobber3Class();
            Assert.AreEqual(7, robber.Rob(root));
        }
    }

    public class HouseRobber3Class
    {
        //we can't rob directly connected nodes.
        // so we can rob root which is level 1 + level 3
        // or only level 2 which is root.left+root.right
        // we need to find the max of the two
        public int Rob(TreeNode root)
        {
            return Helper(root, new Dictionary&lt;TreeNode, int&gt;());
        }

        public int Helper(TreeNode root, Dictionary&lt;TreeNode, int&gt; hash)
        {
            if (root == null)
            {
                return 0;
            }

            if (hash.ContainsKey(root))
            {
                return hash[root];
            }

            int sum = 0;
            if (root.left != null)
            {
                sum += Helper(root.left.left, hash) + Helper(root.left.right, hash);
            }

            if (root.right != null)
            {
                sum += Helper(root.right.left,hash) + Helper(root.right.right, hash);
            }

            sum =  Math.Max(root.val + sum, Helper(root.left, hash) + Helper(root.right, hash));
            hash.Add(root, sum);
            return sum;


        }
    }
}
Your testcases are far too simple to be certain your algorithm works. This might be an issue on the challenge's side. Both these testcases have symmetrical solutions. For these testcases, it's best to always rob every second layer. No test cases cover instances where the left side of the tree might follow a different pattern to the right side. Take for example the testcase:

{ 3, 8, 5, 1, 3, 10, 1 }


On the left branch, you'd expect the 8 to be robbed on the second layer, while the right side is more beneficial to rob the third layer, foregoing the first layer altogether. 

That said, your algorithm appears to handle this correctly. That, along with the caching you do, appears to be working quite well.