666. Path Sum IV
If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.
For each integer in this list:
The hundreds digit represents the depth D of this node, 1 <= D <= 4.
The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
The units digit represents the value V of this node, 0 <= V <= 9.
Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.
Example 1:
|
1 2 3 4 5 6 7 8 9 10 |
Input: [113, 215, 221] Output: 12 Explanation: The tree that the list represents is: 3 / \ 5 1 The path sum is (3 + 5) + (3 + 1) = 12. |
Example 2:
|
1 2 3 4 5 6 7 8 9 10 |
Input: [113, 221] Output: 4 Explanation: The tree that the list represents is: 3 \ 1 The path sum is (3 + 1) = 4. |
Answer
In my view, this is a simple tree’s route problem, we can choose DFS or BFS to solve it. What’s the hard is that we should transfer Integer to a valid tree structs.
But , we can use a reserved BFS to solve the problem. And using a array int[] time to record visited times of each node.
Like the Example 1, now that two leaf nodes has no child node, they should be visited just once. And the root node has two leaves, so it should be visited twice.
In my code, I used (nums[j]/100==nums[i]/100-1)&&((nums[j])/10)%10==((nums[i]/10)%10+1)/2) to judge if current node has parent node.
– the former judges the layer of parent node and the latter judges if the it’s position.
the visited time of parent node is the sum of its both child node visited time, and finally we can add them together to get result.
Code is following:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int pathSum(int[] nums) { if(nums.length==0) return 0; if(nums.length==1) return nums[0]%10; int res =0 ; int[] time = new int[nums.length]; for(int i=nums.length-1;i>=0;i--){ for(int j=i-1;j>=0;j--){ if(time[i]==0) time[i]=1; if((nums[j]/100==nums[i]/100-1)&&((nums[j])/10)%10==((nums[i]/10)%10+1)/2){ time[j]+=time[i]; } } } for(int i=0;i<nums.length;i++){ res +=nums[i]%10 * time[i]; } return res; } } |