337. House Robber III | LeetCode Medium | Python Solution | Tree, DFS, Dynamic Programming смотреть онлайн

Leetcode medium problem 337. House Robber III, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/house-robber-iii/
Solution (Python Code): https://github.com/shaheershukur/LeetCode-Python-Solutions/blob/main/Python%20Solutions/337.%20House%20Robber%20III.py

House Robber: https://youtu.be/Yhm6Y8trVn4
House Robber II: https://youtu.be/NhZsWqyMYj0

#leetcode #python #solution

Problem Statement:
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given a binary tree, in which each node represents a house continaing some amount of money.
we need to rob maximum amount of money from this binary tree, such that we do not rob from two adjacent nodes.

at each node in the tree, we have two options. we can either rob the node, or not rob the node.

if we are robbing the current node, then we cannot rob the immediate left node and immediate right node, because they both are adjacent to the current node.
therefore, the maximum amount of money we can rob will be the amount of money present in the current node + the amount of money we could rob without robbing the immediate left node + the amount of money we could rob without robbing the immediate right node.

and if we are not robbing the current node, then in that case, we can either rob or not rob the immediate left node and right node.
therefore, the maximum amount of money we can rob will be, the maximum of the amount we get with and without robbing the immediate left node + the maximum of the amount we get with and without robbing the immediate right node.

so, for each node, we will be finding out the amount of money we can rob when taking and not taking that node.
we will start finding it from the bottom of the tree, and once we reach the root of the tree, we will choose the maximum amount of money we can rob when taking or not taking the root of the tree.

now lets code the solution.

we will recursively traverse through the tree starting from the root node.
we will write a seperate function to recursively traverse the tree.

for the current node, we need to find out the maximum amount of money we can rob by taking the current node, and by not taking the current node.
and, at last, we will be returning it as a tuple.
ie, at index 0, we will have the amount when taking the current node.
and at index 1, we will have the amount when not taking the current node.

also, in the beggining, we must recursively call this function on the left and right nodes.

now, coming back to the current node, we know that, if we are taking the current node, then the maximum amount of money we can rob is the amount of money present in the current node + the amount of money we could rob without taking the immediate left node + the amount of money we could rob without taking the immediate right node.

and if we are not taking the current node, then the maximum amount of money we can rob is the maximum of the amount we get with and without taking the immediate left node + the maximum of the amount we get with and without robbing the immediate right node.

at last, once the function ends recursively at the root of the tree, we can return the maximum of the amount we get with or without taking the root node.