他雖然AC了但是用的方法不太好，因此跑來問我有沒有看起來很帥速度又快的方法。
因為網路上的code都用一些很慢的方法來建樹，很多都$\ord{N^2}$，雖然也有看似$\ord{N}$的方法，但是用到像是unordered_map之類常數很大也不保證複雜度是$\ord{1}$(codeforces會卡內建hash)。
因為我查到的code都太糟糕了，因此我決定自己寫一個複雜度保證為$\ord{N}$又好寫的方法。
首先是找$root$的部分，因為有給後序的關係很容易就是到是誰了，但是找左右子樹就會出問題。經過觀察，只需要在dfs的過程用stack紀錄一些特別點就可以好好地維護左右子樹。
假設現在dfs在點$u$，stack紀錄的點就是從$root$到$u$的路徑所有點中，除了那些左小孩也在該路徑中的點之外的所有點，有點複雜看個圖會比較明白，紅色的點就是記錄在stack中的點。
至於為什麼記錄這些點就可以在dfs時判斷現在是不是NULL的節點，以及如果給的是preorder的情況就交給讀者思考了
以下附上程式碼:
沒有留言:
張貼留言