原题链接在这里:https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/description/
题目:
Given the root
of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.
Note:
- The average of
n
elements is the sum of then
elements divided byn
and rounded down to the nearest integer. - A subtree of
root
is a tree consisting ofroot
and all of its descendants.
Example 1:
Input: root = [4,8,5,0,1,null,6] Output: 5 Explanation: For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4. For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5. For the node with value 0: The average of its subtree is 0 / 1 = 0. For the node with value 1: The average of its subtree is 1 / 1 = 1. For the node with value 6: The average of its subtree is 6 / 1 = 6.
Example 2:
Input: root = [1] Output: 1 Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]
. 0 <= Node.val <= 1000
题解:
DFS return sum of values in substree and count of nodes in subtree.
when sum/count == root.val, incremental the result by 1.
Time Complexity: O(n). n is the number of nodes in the tree.
Space: O(h). h is the height of the tree.
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 int res = 0; 18 public int averageOfSubtree(TreeNode root) { 19 dfs(root); 20 return res; 21 } 22 23 private int[] dfs(TreeNode root){ 24 if(root == null){ 25 return new int[]{0, 0}; 26 } 27 28 int[] l = dfs(root.left); 29 int[] r = dfs(root.right); 30 int sum = l[0] + r[0] + root.val; 31 int count = l[1] + r[1] + 1; 32 if(sum / count == root.val){ 33 res++; 34 } 35 36 return new int[]{sum, count}; 37 } 38 }标签:Count,TreeNode,val,int,Average,Equal,subtree,root,average From: https://www.cnblogs.com/Dylan-Java-NYC/p/18086980