Day 18：501. Find Mode in Binary Search Tree

今日题目

题目连结：501. Find Mode in Binary Search Tree
题目主题：Tree, Depth-First Search, Binary Search Tree, Binary Tree

今天的主题虽然放在Binary Search Tree，但题目的实作上其实也是在复习Depth-First Search。

简单说说 Binary Search Tree With Duplicates

在前面文章中提过Binary Search Tree的其中一个原则是不会有节点出现重复的值，但有时候会有例外，例如本题就提到，这是一个会有重复节点的Binary Search Tree，下图是一个Binary Search Tree With Duplicates的范例：

上图中可以看到，除了 9 有出现重复以外，其他条件都还是符合 Binary Search Tree 的原则。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一颗 Binary Search Tree With Duplicates，目的是在这棵树中找出重复最多次的值，最终要回传这棵树出现最多次的值，若有两个以上值同样是出现最多次的，需要全部都回传。

约束：

• 树的节点总数范围在[1, 10的4次方]
• -10的5次方 <= Node.val <= 10的5次方

范例1

输入：root = [1,null,2,2]
输出：[2]

范例2

输入：root = [0]
输出：[0]

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法，传入要前往的节点及一个map
2. 递回方法会用Preorder Traversal的方式走完整棵树，并且最後回传一个完整的map。map会记录每个值出现的次数。
3. 确认map被记录到最多次数的数字
4. 回传所有出现最多次数的值

图解过程

范例：root = [1, -10, 9, -10, -3, 9, 13]

上图中，step1 ~ step7 是用Preorder的方式走的过程，可以看到每一轮都会把现在的值放进map看目前这个值有几个，map中的方框资料左边为 key 是目前的值、右边为 value 是这个值现在出现过几次的数字。

可以特别看看 step5 ～ step6 的过程，在 step5 时因为 map 中还没有 9 这个值出现，因此放一个 9 进去这个 map，到 step6 可以看到 因为 map 中已经有 9 了，所以直接把 9 的出现次数 +1。

最後整棵树走过一次以後，看到 step8 ~ step9，在step8 用map可以看到 -10 跟 9 都出现过两次，没有比他们的出现次数还要更多的值了，step9 就是最後要输出的结果。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def traversal(self, node: Optional[TreeNode], map):
        if node == None: return map
        # 如果有节点，将值放进map中
        if node.val in map:
            map[node.val] += 1
        else:
            map[node.val] = 1
        # 继续往左边节点去确认值
        map = self.traversal(node.left, map)
        # 继续往右边节点去确认值
        map = self.traversal(node.right, map)
        
        return map
        
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        map = self.traversal(root, {})
        # 确认最多出现次数的数字
        maxValue = max(map.values())
        # 从map把所有出现次数最多的值都回传
        return [key for key in map.keys() if map[key] == maxValue]

希望您今天能了解到...

1. Binary Search Tree With Duplicates
2. 501. Find Mode in Binary Search Tree的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：1534. Count Good Triplets