Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /**
- * Recursive Greedy Solution.
- *
- * Time Complexity: O(N)
- *
- * Space Complexity: O(N)
- *
- * N = Number of nodes in the tree.
- */
- class Solution {
- public int rob(TreeNode root) {
- if (root == null) {
- return 0;
- }
- int[] result = robHelper(root);
- return Math.max(result[0], result[1]);
- }
- private int[] robHelper(TreeNode node) {
- if (node == null) {
- return new int[2];
- }
- int[] left = robHelper(node.left);
- int[] right = robHelper(node.right);
- int[] res = new int[2];
- res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
- res[1] = node.val + left[0] + right[0];
- return res;
- }
- }
Add Comment
Please, Sign In to add comment