網頁

2014年3月1日 星期六

UVa 10821 Constructing BST

想法:
    在最上層的時候,假設我們有數列{1,2,3,4,5,6,7},要選出一個數字當作該層的root,例如選擇'4',那麼{1,2,3}就被分配到左子樹,{4,5,6}到右子樹,到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root,然後繼續到下一層。
    但題目有說輸出要盡可能小,所以選擇root的時候,要盡可能選靠左邊的數字,所以要讓右子樹填滿,例如現在最上層數列為{1,2,3,4,5,6},深度H=3,代表子樹深還有2,則左右子樹各別能提供(2^2-1=3)3個空間,因此我們選擇'3'當作root,分成{1,2}和{4,5,6}到左右子樹,讓右子樹3個空間被填滿,一直遞迴下去直到分配完全部數字。