question 1 逆序遍歷二分樹
給定一個(gè)二分搜索樹（BST），對于每一個(gè)節(jié)點(diǎn)，加上所有比它大的節(jié)點(diǎn)的和，然后返回這個(gè)樹
我的答案：
一個(gè)很直接的想法就是先將樹轉(zhuǎn)換成列表，這樣就能很容易的得到大小的信息，然后再遍歷一次樹，將比當(dāng)前節(jié)點(diǎn)大的值加上就可以。
可以看到，首先這樣子做需要瀏覽兩次樹(2*n)，同時(shí)將節(jié)點(diǎn)列表排序時(shí)間復(fù)雜度為O(n),轉(zhuǎn)換成hash表為O(n)
所以總共的時(shí)間復(fù)雜度為 4*n
平均運(yùn)行一次要150ms左右，速度在整體答案里排后30%
實(shí)際上對于一個(gè)二分樹，可以直接遍歷一次樹就得到順排或者逆序排的列表：
如上的遞歸遍歷，直接遞歸到最右的子節(jié)點(diǎn)，提取值，再依次返回父節(jié)點(diǎn)，提取值，左子節(jié)點(diǎn)，提取值
別人的方法：
實(shí)際上，仔細(xì)想一想上面的方法，真的需要遍歷兩次樹嗎？
第一次遍歷得到了一個(gè)從大到小排列的列表，第二次遍歷將節(jié)點(diǎn)的值加上所有比這個(gè)節(jié)點(diǎn)大的節(jié)點(diǎn)值之和（這樣需要找一個(gè)方便的查找方法，上面用了hash查找）
但是實(shí)際上第一次遍歷的時(shí)候就可以得到所有比這個(gè)節(jié)點(diǎn)大的節(jié)點(diǎn)之和的信息(因?yàn)锽ST節(jié)點(diǎn)大小關(guān)系? left<root<right),只要遍歷方式是從大到小遍歷，就只需要一個(gè)變量將大的節(jié)點(diǎn)和累加到小的節(jié)點(diǎn)上，就可以達(dá)到目標(biāo)
這樣的時(shí)間復(fù)雜度為O(n)，同時(shí)也可以看到深度優(yōu)先搜索（DFS）的代碼比廣度優(yōu)先搜索（BFS）簡潔很多
question 2 列表查找
給定一個(gè)從 1~n的列表，其中有一個(gè)數(shù)是重復(fù)的，找出這個(gè)數(shù)
我的方法：
其中涉及到兩個(gè)問題：列表查重，列表查缺
因?yàn)橐呀?jīng)知道數(shù)據(jù)一點(diǎn)是從 1~n的，只是有一個(gè)不同，所以用set就能找到缺的那個(gè)數(shù)。而對于重復(fù)的數(shù)，直接用字典計(jì)數(shù)
別人的方法：
因?yàn)橹皇且粋€(gè)數(shù)不一樣，可以用數(shù)學(xué)方法解決
因?yàn)?1~n的列表和為 (1+n)*n/2,從這里下手
question 3 字符串查找
給定一個(gè)字符串和詞根列表，要求將字符串內(nèi)的詞替換成詞根
我的答案：
一個(gè)很直觀的想法是將一句話分成一個(gè)個(gè)的詞，對每一個(gè)詞都在字典中查詢是否存在詞根。注意題目說的是詞根在詞的前面，所以對于每一個(gè)詞從開頭開始查詢
這里需要注意的是為什么要把詞根轉(zhuǎn)換成set查詢而不是list查詢？
因?yàn)閟et里面也是hash結(jié)構(gòu)的，和dict唯一不同的地方是其沒有key,所以在set里面查找的時(shí)間復(fù)雜度是o(1)
用集合查找的方法對于一個(gè)長度為n的詞需要查詢n次，假如這句子有m個(gè)詞，則時(shí)間復(fù)雜度為
O(n*m)
新東西：字典樹
https://leetcode.com/problems/implement-trie-prefix-tree/#/description
字典樹（Trie）在字符串查詢中很常見，比如搜索引擎的補(bǔ)全功能
其查詢一個(gè)詞（word）是否存在于數(shù)中的時(shí)間復(fù)雜度為 O(len(word))
假如我們對這道題目用字典樹，這樣只需要對給定的root建立字典樹，然后對每個(gè)詞在樹內(nèi)搜索就可以了，時(shí)間復(fù)雜度為
O( 詞長度n*句子詞數(shù)量m)
而用列表查找的方法（第一種解法），對一個(gè)詞需要查找 n中可能組合
O( 詞長度n*詞根數(shù)量t*句子詞數(shù)量m)
字典樹數(shù)據(jù)結(jié)構(gòu)
答案：
