中序遍歷簡單變形可以得到求第K大的算法O(nlogn)
前序遍歷可以在O(n)時間內(nèi)完成二叉樹的構(gòu)建,因為在構(gòu)建第二個二叉樹的時候,插入一個節(jié)點不需要從頭開始,要添加的節(jié)點的父節(jié)點是已知的,所以這部分logn的時間變成O(1)的時間。
前序遍歷可以在O(n)時間內(nèi)完成二叉樹的構(gòu)建,因為在構(gòu)建第二個二叉樹的時候,插入一個節(jié)點不需要從頭開始,要添加的節(jié)點的父節(jié)點是已知的,所以這部分logn的時間變成O(1)的時間。
2021-01-04
這個demo的數(shù)組 還是過于巧合
[8, 3 10, 1, 6 , 14, 4, 7, 13]
這個剛好是前序遍歷,如果數(shù)組里面的元素沒有規(guī)則,
那么勢必就會存在 需要在中間插入節(jié)點的情況,
所以這個節(jié)點構(gòu)造的函數(shù) 還是太過于理想
[8, 3 10, 1, 6 , 14, 4, 7, 13]
這個剛好是前序遍歷,如果數(shù)組里面的元素沒有規(guī)則,
那么勢必就會存在 需要在中間插入節(jié)點的情況,
所以這個節(jié)點構(gòu)造的函數(shù) 還是太過于理想
2020-10-18
我用自己的電腦測試發(fā)現(xiàn)。
構(gòu)建二叉樹的時間 大約是 三種排序時間的2-3倍。
三種排序之間的平均時間差不大。
而且電腦最多可以操作1千萬個數(shù)。再多,瀏覽器就崩潰了。
構(gòu)建二叉樹的時間 大約是 三種排序時間的2-3倍。
三種排序之間的平均時間差不大。
而且電腦最多可以操作1千萬個數(shù)。再多,瀏覽器就崩潰了。
2020-09-29
這個真還是有點繞,主要是removeNode這個函數(shù),在某個子樹中刪除某個節(jié)點,參數(shù)1:子樹的根節(jié)點, 參數(shù)2:刪除值為多少的節(jié)點, 返回刪除該節(jié)點后的子樹根節(jié)點
2020-06-17
前序 父* -> 左 -> 父 -> 右 ->父
中序 父 -> 左 -> 父* -> 右 ->父
后序 父 -> 左 -> 父 -> 右 ->父*
中序 父 -> 左 -> 父* -> 右 ->父
后序 父 -> 左 -> 父 -> 右 ->父*
2020-06-17