更新 0501.二叉搜索树中的众数 go版（原先的写法有问题，过不了leetcode）

NevS · web-flow · commit f85d1c1a3792 · 2021-06-29T22:41:40.000+08:00
原先的写法有问题，过不了leetcode，更新正确的解法
diff --git a/problems/0501.二叉搜索树中的众数.md b/problems/0501.二叉搜索树中的众数.md
@@ -474,7 +474,7 @@ func traversal(root *TreeNode,history map[int]int){
 }
 ```
 
-计数法BSL（此代码在执行代码里能执行，但提交后报错，不知为何，思路是对的）
+计数法，不使用额外空间，利用二叉树性质，中序遍历
 
 ```go
 /**
@@ -485,41 +485,35 @@ func traversal(root *TreeNode,history map[int]int){
  *     Right *TreeNode
  * }
  */
- var count,maxCount int //统计计数
-func findMode(root *TreeNode) []int {
-    var result []int
-    var pre *TreeNode //前指针
-    if root.Left==nil&&root.Right==nil{
-        result=append(result,root.Val)
-        return result
-    }
-    traversal(root,&result,pre)
-    return result
-}
-func traversal(root *TreeNode,result *[]int,pre *TreeNode){//遍历统计
-      //如果BSL中序遍历相邻的两个节点值相同，则统计频率；如果不相同，依据BSL中序遍历排好序的性质，重新计数
-    if pre==nil{
-        count=1
-    }else if pre.Val==root.Val{
-        count++
-    }else {
-        count=1
-    }
-    //如果统计的频率等于最大频率，则加入结果集；如果统计的频率大于最大频率，更新最大频率且重新将结果加入新的结果集中
-    if count==maxCount{
-        *result=append(*result,root.Val)
-    }else if count>maxCount{
-        maxCount=count//重新赋值maxCount
-        *result=[]int{}//清空result中的内容
-        *result=append(*result,root.Val)
-    }
-    pre=root//保存上一个的节点
-    if root.Left!=nil{
-        traversal(root.Left,result,pre)
+ func findMode(root *TreeNode) []int {
+    res := make([]int, 0)
+    count := 1
+    max := 1
+    var prev *TreeNode
+    var travel func(node *TreeNode) 
+    travel = func(node *TreeNode) {
+        if node == nil {
+            return
+        }
+        travel(node.Left)
+        if prev != nil && prev.Val == node.Val {
+            count++
+        } else {
+            count = 1
+        }
+        if count >= max {
+            if count > max && len(res) > 0 {
+                res = []int{node.Val}
+            } else {
+                res = append(res, node.Val)
+            }
+            max = count
+        }
+        prev = node
+        travel(node.Right)
     }
-    if root.Right!=nil{
-        traversal(root.Right,result,pre)
-    } 
+    travel(root)
+    return res
 }
 ```
 
