[LeetCode]Path Sum IV

既然题目给定了我们输入每一个节点的深度和位置我们就可以重构出这个树，这里我们用map来表示即可，key为对应节点的位置，value为存了所有子节点的vector。之后我们用BFS求所有的path和即可。时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int pathSum(vector<int>& nums) {
	int len = nums.size(), res = 0, i = 1;
	if(!len)return 0;
	unordered_map<int, vector<int>> tree;
	for(auto&& num : nums)
	{
	int pos = num / 10, parent = (pos / 10 - 1) * 10 + (pos % 10 + 1) / 2;
	if(tree.find(parent) != tree.end())
	tree[parent].push_back(num);
	tree[pos] = {};
	}
	queue<pair<int, int>> q;
	q.push(make_pair(nums[0], nums[0] % 10));
	while(q.size())
	{
	int size = q.size();
	while(size--)
	{
	auto curr = q.front();
	q.pop();
	if(tree[curr.first / 10].size())
	{
	for(int child : tree[curr.first / 10])
	q.push(make_pair(child, curr.second + child % 10));
	}
	else
	res += curr.second;
	}
	}
	return res;
	}
	};

view raw Path Sum IV.cpp hosted with ❤ by GitHub