//
// Created by Mr.Hu on 2018/12/13.
//
// leetcode 501 find mode in binary search tree
//
// 题目要求对给定的二叉搜索树,找出所有出现次数最多的元素;
// 二叉搜索树的定义,节点的值大于等于左子树上所有节点的值,小于等于右子树所有节点的值。
//
// 我先使用蛮力法进行解决,对该树使用BFS(广度优先搜索)的方式,逐层遍历每个节点,使用map数据结构存储每个节点值的出现次数,
// 同时更新当前最多出现次数。遍历完整棵树后,在map中找出出现次数等于最多出现次数的key值,即为题目要求的mode(s)集合
// 这种方式借助了大量的外部存储空间,这不满足题目所期望的不使用额外存储空间。
//
// 关于不使用额外存储空间的思考:上面的方法对整棵树进行遍历,最终得到每个节点值出现的次数。我们并没有用到这棵树是二叉搜索树这样一个条件,
// 上面的方法对任意一颗二叉树都可以使用。所以这一点是我们可以思考的地方。。。
//
// recursion solution
// leetcode 的 discussion 中有很很多都是使用map solution,只是在遍历的过程中,没有使用queue来存储当前节点,直接使用recursion的方式
// 遍历每一个节点,并使用map记录每个节点值出现的次数。
//
1 |
|