Solution to Path In Tree from Jobdu

18 Aug

Question (in Chinese):

Question Name: Path In Tree

Question Description: Given a binary tree and a value, show all the paths, whose sum is equal to the given value. A path is defined as the route from root to one leaf.

Input: the input might contain multiple test cases. Each test case includes N+1 lines. Inside each test case, the first line includes two intergers N and K (0 <= N <= 10000). N is the number of nodes in that tree. And K is the wanted sum. The following N lines contain three integers in each line as vi, leftnode, and rightnode. vi is the value of the i(th) node. leftnode and rightnode are the indexes of i(th) node’s left son and right son respectively. -1 means no such son.

Output: firstly print out a line “result:”, then print out all the qualified paths lexicographically.

The solution is:

Leave a Reply

Your email address will not be published. Required fields are marked *