House Robber III
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.
public class Solution {
public int rob(TreeNode root) {
int[] num = dfs(root);
return Math.max(num[0], num[1]);
}
private int[] dfs(TreeNode x) {
if (x == null) return new int[2];
int[] left = dfs(x.left);
int[] right = dfs(x.right);
int[] res = new int[2];
res[0] = left[1] + right[1] + x.val;
res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return res;
}
}Related Problems
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Given a string s, return the longest palindromicsubstringin s.
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).