Merge pull request youngyangyang04#490 from Miraclelucy/master

youngyangyang04 · web-flow · commit 7625216d72fe · 2021-07-14T15:37:34.000+08:00
Update 0501.二叉搜索树中的众数.md - 增加了python3版本的迭代解法
diff --git a/problems/0501.二叉搜索树中的众数.md b/problems/0501.二叉搜索树中的众数.md
@@ -435,7 +435,7 @@ Python：
 #         self.val = val
 #         self.left = left
 #         self.right = right
-//递归法
+# 递归法
 class Solution:
     def findMode(self, root: TreeNode) -> List[int]:
         if not root: return
@@ -460,6 +460,66 @@ class Solution:
             return
         findNumber(root)
         return self.res
+	
+
+# 迭代法-中序遍历-使用额外空间map的方法：
+class Solution:
+    def findMode(self, root: TreeNode) -> List[int]:
+        stack = []
+        cur = root
+        pre = None
+        dist = {}
+        while cur or stack:
+            if cur:  # 指针来访问节点，访问到最底层
+                stack.append(cur)
+                cur = cur.left
+            else:  # 逐一处理节点
+                cur = stack.pop()
+                if cur.val in dist:
+                    dist[cur.val] += 1
+                else:
+                    dist[cur.val] = 1
+                pre = cur
+                cur = cur.right
+
+        # 找出字典中最大的key
+        res = []
+        for key, value in dist.items():
+            if (value == max(dist.values())):
+                res.append(key)
+        return res
+
+# 迭代法-中序遍历-不使用额外空间，利用二叉搜索树特性：
+class Solution:
+    def findMode(self, root: TreeNode) -> List[int]:
+        stack = []
+        cur = root
+        pre = None
+        maxCount, count = 0, 0
+        res = []
+        while cur or stack:
+            if cur:  # 指针来访问节点，访问到最底层
+                stack.append(cur)
+                cur = cur.left
+            else:  # 逐一处理节点
+                cur = stack.pop()
+                if pre == None:  # 第一个节点
+                    count = 1
+                elif pre.val == cur.val:  # 与前一个节点数值相同
+                    count += 1
+                else:
+                    count = 1
+                if count == maxCount:
+                    res.append(cur.val)
+                if count > maxCount:
+                    maxCount = count
+                    res.clear()
+                    res.append(cur.val)
+
+                pre = cur
+                cur = cur.right
+        return res	
+	
 ```
 Go：
 暴力法（非BSL）
