**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;
}
```