112. 路径总和

题目链接(https://leetcode-cn.com/problems/path-sum/)

二叉树这种题目个人认为从代码的简洁性来说，不用递归用BFS的话，是没有灵魂的。

之所以是简答题，是因为我们只需要遍历一下就行了，而不需要关心每层的位置怎么摆放。递归调用的话，设置一个二维数组，这个数组的行为二叉树的深度，共两列，第0代表当前行共有多少个数，第1行代表当前行所有数的总和。详情见代码。

class Solution {
public:

	vector<vector<int>> v;//二维数组，行为二叉树的层数，共一列，代表二叉树的

	void dfs(TreeNode* root, int k)
	{
		if (root == NULL) return;

		if (k > v.size())
		{
			v.push_back(make_pair(0, 0));
		}
		v[k - 1].first = v[k - 1].first + root->val;
		v[k - 1].second = v[k - 1].second + 1;//统计次数
		dfs(root->left, k + 1);
		dfs(root->right, k + 1);
	}

	vector<double> averageOfLevels(TreeNode* root) {
		dfs(root, 1);
		vector<double> ret;
		for (auto i : v)
		{
			ret.push_back((i.first)*1.0 / (i.second));
		}
		return ret;
	}
};