{"id":"db25321c-2b0e-43d4-ba2a-6773a4a4ebce","name":"House Robber In Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. 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\". \r\nIt will automatically contact the police if two directly-linked houses were broken into on the same night.\r\nDetermine the maximum amount of money the thief can rob tonight without alerting the police.\r\n3. Input and Output is managed for you.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint HouseRobber(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n cout << HouseRobber(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static int HouseRobber(TreeNode root) {\r\n return 0;\r\n }\r\n\r\n // input_Section_====================================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1){\r\n IDX[0]++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n System.out.println(HouseRobber(root));\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"4\r\n","questionVideo":"https://www.youtube.com/embed/kTL5LhCTL1c","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"73807050-2dec-40f3-a154-a93f09fe4b13","name":"House Robber In Binary Tree","slug":"house-robber-in-binary-tree","type":1}],"next":{"id":"652f204d-ab7d-4ff0-b1ba-3853dcdc9bf4","name":"House Robber In Binary Tree","type":3,"slug":"house-robber-in-binary-tree"},"prev":{"id":"bfe3c5f1-5922-477c-a55c-78cbb015ea40","name":"Cameras In Binary Tree","type":0,"slug":"cameras-in-binary-tree"}}}

House Robber In Binary Tree

1. You are given a partially written function to solve. 2. 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. 3. Input and Output is managed for you.

{"id":"db25321c-2b0e-43d4-ba2a-6773a4a4ebce","name":"House Robber In Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. 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\". \r\nIt will automatically contact the police if two directly-linked houses were broken into on the same night.\r\nDetermine the maximum amount of money the thief can rob tonight without alerting the police.\r\n3. Input and Output is managed for you.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint HouseRobber(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n cout << HouseRobber(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static int HouseRobber(TreeNode root) {\r\n return 0;\r\n }\r\n\r\n // input_Section_====================================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1){\r\n IDX[0]++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n System.out.println(HouseRobber(root));\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"4\r\n","questionVideo":"https://www.youtube.com/embed/kTL5LhCTL1c","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"73807050-2dec-40f3-a154-a93f09fe4b13","name":"House Robber In Binary Tree","slug":"house-robber-in-binary-tree","type":1}],"next":{"id":"652f204d-ab7d-4ff0-b1ba-3853dcdc9bf4","name":"House Robber In Binary Tree","type":3,"slug":"house-robber-in-binary-tree"},"prev":{"id":"bfe3c5f1-5922-477c-a55c-78cbb015ea40","name":"Cameras In Binary Tree","type":0,"slug":"cameras-in-binary-tree"}}}
plane

Editor

Loading...

House Robber In Binary Tree

easy

1. You are given a partially written function to solve. 2. 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. 3. Input and Output is managed for you.

Constraints

0 <= Number of Nodes <= 10^9 -10^9 <= value of Node data <= 10^9

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

15 1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1

Sample Output

4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode