LeetCode: House Robber III C#

Question

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
{
    /// <summary>
    /// https://leetcode.com/problems/house-robber-iii/
    /// </summary>
/**
 * 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<TreeNode, int>());
        }

        public int Helper(TreeNode root, Dictionary<TreeNode, int> 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;


        }
    }
}

I really have no idea wherefore the spec is asking here: could you clarify what the actual problem is, because the fluff isn't helping. What do the numbers in the tree mean? What constitutes breaking in? — VisualMelon
– VisualMelon, Commented Sep 20, 2019 at 11:41
so you can only get a sum from level 1 + 3 because they are not directly connected, or the sum of level 2. so you basically need to rob levels of the tree which are not connected and get the maximum sum. — Gilad
– Gilad, Commented Sep 20, 2019 at 11:43
@dfhwze I am just trying to make this clearer, you guys, I didn't invent anything ... this is the way leetcode phrase this. — Gilad
– Gilad, Commented Sep 20, 2019 at 12:22
@Gilad I edited your post so the whole thing is easier to read, I hope you don't mind. Otherwise, don't hesitate to rollback the edit — IEatBagels
– IEatBagels, Commented Sep 20, 2019 at 14:29
Also, if i may offer an explanation of what I understood. You cannot rob two houses that are connected (that is, parent/child or child/parent). So, in the first example, you can rob house 3, meaning you can't rob anything in the second "level", because both are connected to the node 3 that we just robbed. We can then rob the third "level"' because they aren't directly connected to the node 3 that we just robbed. Maybe you can try to use this more "step by step" explanation in your post to make it clearer. — IEatBagels
– IEatBagels, Commented Sep 20, 2019 at 14:32

JAD · Accepted Answer · 2019-10-25 08:46:32Z

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.

Martin R · Accepted Answer · 2019-10-24 21:09:47Z

The

public int Helper(TreeNode root, Dictionary<TreeNode, int> hash)

method can (and should) be private. It is not meant to be called from outside the class.

The helper method would also benefit from a (short) explaining comment: How does the recursion work, and what is cached?

The helper method does 6 recursive calls to itself. A dictionary is used to cache the results, so that the tree is essentially traversed only once, but that dictionary has to be passed down in the recursive calls.

A slightly different approach makes the cache obsolete and reduces the numbers of recursive calls. The idea is to compute two sums for every node:

the maximal amount that can be achieved by robbing this house, and
the maximal amount that can be achieved by not robbing this house.

The implementation is simple and almost self-explaining:

public int Rob(TreeNode root)
{
    var (with, without) = Helper(root);
    return Math.Max(with, without);
}

// Recursively determine the maximal amount that can be achieved
// - by robbing this house,
// - by skipping this house.
private (int, int) Helper(TreeNode root)
{
    if (root == null)
    {
        return (0, 0);
    }

    var (leftWith, leftWithout) = Helper(root.left);
    var (rightWith, rightWithout) = Helper(root.right);

    // If we rob this house then we cannot rob its immediate children:
    var sumWith = root.val + leftWithout + rightWithout;
    // Otherwise we can rob the immediate children (and pick the
    // maximal possible sum for both):
    var sumWithout = Math.Max(leftWith, leftWithout) + Math.Max(rightWith, rightWithout);

    return (sumWith, sumWithout);
}

Stack Exchange Network

LeetCode: House Robber III C#

2 Answers 2

You must log in to answer this question.

Hot Network Questions

LeetCode: House Robber III C#

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions