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 7Output: [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.
Answer:
/** * @param {TreeNode} root * @return {number[]} */var averageOfLevels = function(root) { if(root == null) { return 0; } var queue = [];var arr = []; queue.push(root); while(queue.length != 0) { var sum = 0; var count = 0; var temp = []; while(queue.length != 0) { var firstNode = queue.splice(0,1)[0]; sum+= firstNode.val; if(firstNode.left) temp.push(firstNode.left); if(firstNode.right) { temp.push(firstNode.right); } count++; } queue = temp; arr.push(sum/ count); } console.log(arr); return arr; };function TreeNode(val) { this.val = val; this.left = this.right = null;}var rootNode = new TreeNode(3);var lrNode = new TreeNode(9);var rrNode = new TreeNode(20);var lrrNode = new TreeNode(15);var rrrNode = new TreeNode(7);rrNode.right = rrrNode;rrNode.left = lrrNode;rootNode.left = lrNode;rootNode.right = rrNode;averageOfLevels(rootNode);
这里应用BFS的解法。网上还有一种DFS的解法不过还没有研究，就不写了。