主題
題目: 2003. Smallest Missing Genetic Value in Each Subtree
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n)) ，要 O(n) 的請把 set 換掉，改成不斷往上 +1 找洞
題目說明
給一棵樹，樹上有數(shù)字，數(shù)字不重複，且界在 [1,100000] 內(nèi)，問:
對於該樹的每一棵子樹的所有節(jié)點(diǎn)中，從 1 開始往上 +1 找，第 1 個不存在數(shù)字為何。
(所以回傳的數(shù)字有節(jié)點(diǎn)數(shù)量那麼多個)
解法:
1. 因?yàn)槭菑?1 開始找，故子樹中沒有任何一個節(jié)點(diǎn)上的數(shù)字為 1 ，則此子樹的答案為 1 。
2. 專心處理 1 ，從節(jié)點(diǎn)上數(shù)字是 1 的節(jié)點(diǎn)開始，往根的方向填答案。
3. 每次將其他子節(jié)點(diǎn)所構(gòu)成的子樹上的數(shù)字撈起來，看一下最小的"洞"(第一個缺的數(shù)字)是誰。
4. 要 O(n) 時，則除了第一次是從 1 開始找洞以外，其餘時候都是從上次結(jié)果開始往上 +1 來尋找。
source code
5. 至於為什麼寫成用set挖區(qū)間，是因?yàn)槲乙婚_始沒注意到解法中提及的 1. 。
6. 這樣看起來滿簡單的，可是我想好久，這樣算不算是一種鬼故事啊?
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n)) ，要 O(n) 的請把 set 換掉，改成不斷往上 +1 找洞
題目說明
給一棵樹，樹上有數(shù)字，數(shù)字不重複，且界在 [1,100000] 內(nèi)，問:
對於該樹的每一棵子樹的所有節(jié)點(diǎn)中，從 1 開始往上 +1 找，第 1 個不存在數(shù)字為何。
(所以回傳的數(shù)字有節(jié)點(diǎn)數(shù)量那麼多個)
解法:
1. 因?yàn)槭菑?1 開始找，故子樹中沒有任何一個節(jié)點(diǎn)上的數(shù)字為 1 ，則此子樹的答案為 1 。
2. 專心處理 1 ，從節(jié)點(diǎn)上數(shù)字是 1 的節(jié)點(diǎn)開始，往根的方向填答案。
3. 每次將其他子節(jié)點(diǎn)所構(gòu)成的子樹上的數(shù)字撈起來，看一下最小的"洞"(第一個缺的數(shù)字)是誰。
4. 要 O(n) 時，則除了第一次是從 1 開始找洞以外，其餘時候都是從上次結(jié)果開始往上 +1 來尋找。
source code
