# Convert Sorted Array to Binary Search Tree ### Source - leetcode: [Convert Sorted Array to Binary Search Tree | LeetCode OJ](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) - lintcode: [(177) Convert Sorted Array to Binary Search Tree With Minimal Height](http://www.lintcode.com/en/problem/convert-sorted-array-to-binary-search-tree-with-minimal-height/) ~~~ Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height. Example Given [1,2,3,4,5,6,7], return 4 / \ 2 6 / \ / \ 1 3 5 7 Note There may exist multiple valid solutions, return any of them. ~~~ ### 題解 - 折半取中 將二叉搜索樹按中序遍歷即可得升序 key 這個容易實現，但反過來由升序 key 逆推生成二叉搜索樹呢？按照二叉搜索樹的定義我們可以將較大的 key 鏈接到前一個樹的最右側節點，這種方法實現極其簡單，但是無法達到本題「樹高平衡-左右子樹的高度差絕對值不超過1」的要求，因此只能另辟蹊徑以達到「平衡二叉搜索樹」的要求。 要達到「平衡二叉搜索樹」這個條件，我們首先應從「平衡二叉搜索樹」的特性入手。簡單起見，我們先考慮下特殊的滿二叉搜索樹，滿二叉搜索樹的一個重要特征就是各根節點的 key 不小于左子樹的 key ，而小于右子樹的所有 key；另一個則是左右子樹數目均相等，那么我們只要能將所給升序序列分成一大一小的左右兩半部分即可滿足題目要求。又由于此題所給的鏈表結構中僅有左右子樹的鏈接而無指向根節點的鏈接，故我們只能從中間的根節點進行分析逐層往下遞推直至取完數組中所有 key, 數組中間的索引自然就成為了根節點。由于 OJ 上方法入口參數僅有升序序列，方便起見我們可以另寫一私有方法，加入`start`和`end`兩個參數，至此遞歸模型初步建立。 ### C++ ~~~ /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *sortedArrayToBST(vector<int> &num) { if (num.empty()) { return NULL; } return middleNode(num, 0, num.size() - 1); } private: TreeNode *middleNode(vector<int> &num, const int start, const int end) { if (start > end) { return NULL; } TreeNode *root = new TreeNode(num[start + (end - start) / 2]); root->left = middleNode(num, start, start + (end - start) / 2 - 1); root->right = middleNode(num, start + (end - start) / 2 + 1, end); return root; } }; ~~~ ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param A: an integer array * @return: a tree node */ public TreeNode sortedArrayToBST(int[] A) { if (A == null || A.length == 0) return null; return helper(A, 0, A.length - 1); } private TreeNode helper(int[] nums, int start, int end) { if (start > end) return null; int mid = start + (end - start) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums, start, mid - 1); root.right = helper(nums, mid + 1, end); return root; } } ~~~ ### 源碼分析 從題解的分析中可以看出中間根節點的建立至關重要！由于數組是可以進行隨機訪問的，故可取數組中間的索引為根節點，左右子樹節點可遞歸求解。雖然這種遞歸的過程和「二分搜索」的模板非常像，但是切記本題中根據所給升序序列建立平衡二叉搜索樹的過程中需要做到**不重不漏**，故邊界處理需要異常小心，不能再套用`start + 1 < end`的模板了。 ### 復雜度分析 遞歸調用`middleNode`方法時每個`key`被訪問一次，故時間復雜度可近似認為是 O(n)O(n)O(n). ### Reference - [Convert Sorted Array to Binary Search Tree | 九章算法](http://www.jiuzhang.com/solutions/convert-sorted-array-to-binary-search-tree/)