(LeetCode 面试经典 150 题 ) 637. 二叉树的层平均值（深度优先搜索dfs）

思路：深度优先搜索dfs，时间复杂度0(n)。

遍历所有节点，记录每一层的分布情况。

C++版本：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 每层节点值之和vector<double> ans;// 每层的节点数量vector<int> ct;void dfs(TreeNode* root,int d){if(root==nullptr) return;// 当前层遍历到的第一个节点if(ct.size()==d){ct.push_back(1);ans.push_back(root->val);}else{ans[d]+=root->val;ct[d]+=1;}dfs(root->left,d+1);dfs(root->right,d+1);}vector<double> averageOfLevels(TreeNode* root) {dfs(root,0);for(int i=0;i<ans.size();i++){ans[i]/=ct[i];}return ans;}
};

JAVA版本：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Double> ans=new ArrayList<>();List<Integer> ct=new ArrayList<>();void dfs(TreeNode root,int d){if(root==null) return;if(ct.size()==d){ct.add(1);ans.add(root.val*1.0);}else{ans.put(d,root.val+ans.get(d));ct.put(d,1+ct.get(d));}dfs(root.left,d+1);dfs(root.right,d+1);}public List<Double> averageOfLevels(TreeNode root) {dfs(root,0);for(int i=0;i<ans.size();i++){ans[i]/=ct[i];}return ans;}
}

GO版本：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func averageOfLevels(root *TreeNode) []float64 {ans:=[]float64{}ct:=[]int{}dfs(root,0,&ans,&ct)for i:=0;i<len(ct);i++ {ans[i]/=float64(ct[i]);}return ans
}
func dfs(root *TreeNode,d int,ans *[]float64,ct *[]int){if root==nil {return}if len(*ct)==d {*ct=append(*ct,1)*ans=append(*ans,float64(root.Val))}else{(*ct)[d]+=1(*ans)[d]+=float64(root.Val)}dfs(root.Left,d+1,ans,ct)dfs(root.Right,d+1,ans,ct)
}