question 1 逆序遍历二分树

给定一个二分搜索树（BST），对于每一个节点，加上所有比它大的节点的和，然后返回这个树

我的答案：

一个很直接的想法就是先将树转换成列表，这样就能很容易的得到大小的信息，然后再遍历一次树，将比当前节点大的值加上就可以。

可以看到，首先这样子做需要浏览两次树(2*n)，同时将节点列表排序时间复杂度为O(n),转换成hash表为O(n)

所以总共的时间复杂度为 4*n

平均运行一次要150ms左右，速度在整体答案里排后30%

实际上对于一个二分树，可以直接遍历一次树就得到顺排或者逆序排的列表：

如上的递归遍历，直接递归到最右的子节点，提取值，再依次返回父节点，提取值，左子节点，提取值

别人的方法：

实际上，仔细想一想上面的方法，真的需要遍历两次树吗？

第一次遍历得到了一个从大到小排列的列表，第二次遍历将节点的值加上所有比这个节点大的节点值之和（这样需要找一个方便的查找方法，上面用了hash查找）

但是实际上第一次遍历的时候就可以得到所有比这个节点大的节点之和的信息(因为BST节点大小关系  left<root<right),只要遍历方式是从大到小遍历，就只需要一个变量将大的节点和累加到小的节点上，就可以达到目标

这样的时间复杂度为O(n)，同时也可以看到深度优先搜索（DFS）的代码比广度优先搜索（BFS）简洁很多

question 2 列表查找

给定一个从 1~n的列表，其中有一个数是重复的，找出这个数

我的方法：

其中涉及到两个问题：列表查重，列表查缺

因为已经知道数据一点是从 1~n的，只是有一个不同，所以用set就能找到缺的那个数。而对于重复的数，直接用字典计数

别人的方法：

因为只是一个数不一样，可以用数学方法解决

因为 1~n的列表和为 (1+n)*n/2,从这里下手

question 3 字符串查找

给定一个字符串和词根列表，要求将字符串内的词替换成词根

我的答案：

一个很直观的想法是将一句话分成一个个的词，对每一个词都在字典中查询是否存在词根。注意题目说的是词根在词的前面，所以对于每一个词从开头开始查询

这里需要注意的是为什么要把词根转换成set查询而不是list查询？

因为set里面也是hash结构的，和dict唯一不同的地方是其没有key,所以在set里面查找的时间复杂度是o(1)

用集合查找的方法对于一个长度为n的词需要查询n次，假如这句子有m个词，则时间复杂度为

O(n*m)

新东西：字典树

https://leetcode.com/problems/implement-trie-prefix-tree/#/description

字典树（Trie）在字符串查询中很常见，比如搜索引擎的补全功能

其查询一个词（word）是否存在于数中的时间复杂度为 O(len(word))

假如我们对这道题目用字典树，这样只需要对给定的root建立字典树，然后对每个词在树内搜索就可以了，时间复杂度为

O( 词长度n*句子词数量m)

而用列表查找的方法（第一种解法），对一个词需要查找 n中可能组合

O( 词长度n*词根数量t*句子词数量m)

字典树数据结构

答案：