[C++] |Depth First Search | DP with explaination
We construct a dp tree.\nEach node (dp_node) in this dp tree is an array of two elements:\ndp_node = [your gain when you ROB the current node, your gain when yo
We construct a dp tree.\nEach node (dp_node) in this dp tree is an array of two elements:\ndp_node = [your gain when you ROB the current node, your gain when you SKIP the current node]\ndp_node[0] =[your gain when you ROB the current node]\ndp_node[1] =[your gain when you SKIP the current node]\n\nwe start by scanning from the leaf: Depth First Search\n**For each node you have 2 options:\noption 1: ROB the node, then you can\'t rob the child/children of the node.\ndp_node[0] = node.val + dp_node.left[1] + dp_node.right[1]\noption 2: SKIP the node, then you can ROB or SKIP the child/children of the node.\ndp_node[1] = max(dp_node.left[0], dp_node.left[1]) + max(dp_node.right[0], dp_node.right[1])**\n\nthe maximum of gain of the node\n\n```\n    Input: [3,4,5,1,3,null,1]\n input tree            dp tree:\n     3                  [3+3+1,4+5]\n    / \\                /        \\\n   4   5            [4,3]      [5,1]\n  / \\   \\          /     \\          \\\n 1   2   1      [1,0]    [2,0]     [1,0]\n                / \\       /  \\        /  \\\n           [0,0] [0,0] [0,0] [0,0]  [0,0] [0,0]\n   \n``` \n\n```\npair<int,int> helper( TreeNode *node ) {\n\tif( !node ) return {0, 0};\n\n\tauto l = helper( node->left );\n\tauto r = helper( node->right );\n\tint withNode = node->val + l.second + r.second;\n\tint withoutNode = max( r.first, r.second ) + max( l.first, l.second ); \n\treturn { withNode, withoutNode };\n}\n\nint rob( TreeNode* root ) {\n\tauto res = helper( root );\n\treturn max( res.first, res.second );\n}\n```\n
[]