Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].Note:
The range of node's value is in the range of 32-bit signed integer.我的解答：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> v; if(!root){ return v; } queue<TreeNode*> q; q.push(root); while(!q.empty()){ int s = q.size(); long temp = 0; for(int i = 0; i < s; ++i){ TreeNode* tp = q.front(); q.pop(); temp += (long)tp->val; if(tp->left)q.push(tp->left); if(tp->right)q.push(tp->right); } v.push_back(temp/(double)s); } return v; } };利用BFS，二叉树的层次遍历。中间利用一个for循环来达到区分每一层的目的，很巧妙，标记一下。
第104，求一棵二叉数的最深的深度，有种解法，DFS和BFS
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node
BFS /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { int depth = 0; if(!root){ return 0; } queue<TreeNode*> q; q.push(root); while(!q.empty()){ depth++; int s = q.size(); for(int i = 0; i < s; ++i){ TreeNode* temp = q.front(); q.pop(); if(temp->left)q.push(temp->left); if(temp->right)q.push(temp->right); } } return depth; } };其中需要注意的地方是在while循环中的那个for循环，i < s不能写为i < q.size(),因为在循环中q的size()变化了。
//DFS，利用递归,代码很简洁。 int maxDepth(TreeNode *root) { return root == NULL ? 0 : max(maxDepth(root -> left), maxDepth(root -> right)) + 1; } .
