322. Count the Nodes
Foundation1000 ms256 MBSolved by 0%
Print how many nodes the tree has.
The input already tells you: it is n. So compute it by walking the tree
instead, which is the point of the exercise, and use n to check your answer.
The recursion is one node plus the count of each subtree, with an absent
subtree counting 0. That is the same shape as the height with max replaced by
+, and noticing that is worth more than either problem alone.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the number of nodes reachable from the root.
Input3
2 1 3
2 3
0 0
0 0
Output3
Noteis a root with two children
Input1
7
0 0
Output1
Noteis a single node
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution