// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"sort"
)

type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

// 解法1：维护最大频次，不用排序
func findFrequentTreeSum1(root *TreeNode) []int {
	memo := make(map[int]int)
	collectSum(root, memo)
	res := []int{}
	most := 0
	for key, val := range memo {
		if most == val {
			res = append(res, key)
		} else if most < val {
			most = val
			res = []int{key}
		}
	}
	return res
}

func collectSum(root *TreeNode, memo map[int]int) int {
	if root == nil {
		return 0
	}
	sum := root.Data + collectSum(root.Left, memo) + collectSum(root.Right, memo)
	if v, ok := memo[sum]; ok {
		memo[sum] = v + 1
	} else {
		memo[sum] = 1
	}
	return sum
}

// 解法2：求出所有和再排序
func findFrequentTreeSum2(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	freMap, freList, reFreMap := map[int]int{}, []int{}, map[int][]int{}
	findTreeSum(root, freMap)
	for k, v := range freMap {
		tmp := reFreMap[v]
		tmp = append(tmp, k)
		reFreMap[v] = tmp
	}
	for k := range reFreMap {
		freList = append(freList, k)
	}
	sort.Ints(freList)
	return reFreMap[freList[len(freList)-1]]
}

func findTreeSum(root *TreeNode, fre map[int]int) int {
	if root == nil {
		return 0
	}
	if root != nil && root.Left == nil && root.Right == nil {
		fre[root.Data]++
		return root.Data
	}
	val := findTreeSum(root.Left, fre) + findTreeSum(root.Right, fre) + root.Data
	fre[val]++
	return val
}

func main() {
	treeNode := TreeNode{6, &TreeNode{5, nil, nil}, &TreeNode{3, nil, nil}}
	res1 := findFrequentTreeSum1(&treeNode)
	res2 := findFrequentTreeSum2(&treeNode)
	fmt.Println(res1)
	fmt.Println(res2)
}

//$ go run interview4-2.go
//[3 14 5]
//[5 3 14]