切換
舊版
前往
大廳
主題

LeetCode - 108. Convert Sorted Array to Binary Search Tree 解題心得

Not In My Back Yard | 2020-08-16 00:00:07 | 巴幣 0 | 人氣 248

題目連結:


題目意譯:
給定一已將元素按照遞增順序排序後的陣列,將其轉為一棵平衡高度(Height-Balanced)的二元搜尋樹(Binary Search Tree,BST)。

對於此問題,一個平衡高度二元樹定義為:對於任何節點,其兩棵子樹之深度差不超過 1 。



範例測資:
範例:
給定已排序陣列:[-10,-3,0,5,9],

一個可能的答案為:[0,-3,9,-10,null,5],其代表如下的平衡高度二元搜尋樹:
    0
   / \
  -3  2
 /   /
-10 5


解題思維:
因為已經排序了,因此將取陣列中間的元素當作根節點。然後從陣列分成左邊以及右邊的子陣列(因為中間的元素已經建立成一個節點了,所以不應出現於子陣列中)。然後遞迴左邊、右邊的子陣列去分別建成根節點的左子樹以及右子樹(也是同樣的方式)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作