/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
Stack<TreeNode> S = new Stack<TreeNode>();
private void postNode(TreeNode node)
{
if (node != null)
{
S.Push(node);//先序遍历,遍历所有节点
if (node.left != null)
{
postNode(node.left);
}
if (node.right != null)
{
postNode(node.right);
}
}
} private int sumSubTree(TreeNode node)
{
if (node != null)
{
var sum = node.val;
if (node.left != null)
{
sum += sumSubTree(node.left);
}
if (node.right != null)
{
sum += sumSubTree(node.right);
}
return sum;
}
else
{
return ;
} } public int[] FindFrequentTreeSum(TreeNode root)
{
if (root == null)
{
return new int[] { };
}
postNode(root);
var list = S.ToList();
Dictionary<int, int> dic = new Dictionary<int, int>();//key是sum值,value是次数
foreach (var l in list)
{
var sum = sumSubTree(l);
if (!dic.ContainsKey(sum))
{
dic.Add(sum, );
}
else
{
dic[sum]++;
}
} var result = dic.OrderByDescending(x => x.Value).ToList(); var max = int.MinValue;
var arylist = new List<int>();
foreach (var r in result)
{
var count = r.Value;
var cur = r.Key;
if (count >= max)
{
max = count;
arylist.Add(cur);
}
else
{
break;
}
} var ary = arylist.ToArray();
return ary;
}
}
https://leetcode.com/problems/most-frequent-subtree-sum/#/description