Question 1: https://leetcode.com/problems/product-of-array-except-self
Question 2: Variation of https://leetcode.com/problems/random-pick-with-weight
Given a list of cities and the population, pick randomly any city based on the population.
“NY”: 5M, “CA”: 10M, “WS”: 2M
我是这道
Given a complete binary tree , count the number of nodes.
Follow-up:
Given a complete ternary tree , count the number of nodes.
class TreeNode {
TreeNode left;
TreeNode mid;
TreeNode right;
}
Example:
我这么想的
For the full ternary tree, say of height h , the number of nodes n is
n = (3^{h+1} - 1) / 2
Why? Because the first level has 3^0 nodes, the second level has 3^1 nodes, and, in general, the k-th level has 3^{k-1} nodes. Adding these up for a total of h+1 levels (so height h ) gives
n = 3^0 + 3^1 + 3^2 + 3^3 + ... + 3^h = (3^{h+1} - 1) / (3 - 1) = (3^{h+1} - 1) / 2
代码
public static int countNodes(TreeNode root) {
int leftHeight = getHeight(root, true);
int rightHeight = getHeight(root, false);
if (leftHeight == rightHeight) {
return (int) (Math.pow(3, leftHeight) - 1) / 2;
}
return 1 + countNodes(root.left) + countNodes(root.mid) + countNodes(root.right);
}
private static int getHeight(TreeNode node, boolean left) {
int h = 0;
while (node != null) {
h++;
node = left ? node.left : node.right;
}
return h;
}