題目連結:
題目意譯:
給定一已將元素按照遞增順序排序後的陣列,將其轉為一棵平衡高度(Height-Balanced)的二元搜尋樹(Binary Search Tree,BST)。
對於此問題,一個平衡高度二元樹定義為:對於任何節點,其兩棵子樹之深度差不超過 1 。
範例測資:
範例:
給定已排序陣列:[-10,-3,0,5,9],
一個可能的答案為:[0,-3,9,-10,null,5],其代表如下的平衡高度二元搜尋樹:
0
/ \
-3 2
/ /
-10 5
解題思維:
因為已經排序了,因此將取陣列中間的元素當作根節點。然後從陣列分成左邊以及右邊的子陣列(因為中間的元素已經建立成一個節點了,所以不應出現於子陣列中)。然後遞迴左邊、右邊的子陣列去分別建成根節點的左子樹以及右子樹(也是同樣的方式)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。