面试题 04.02. 最小高度树(DFS)

面试题 04.02. 最小高度树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \ 
       -3   9 
       /   / 
     -10  5 

下面是一种构造最小高度树的思路：

1、如果序列长度为 0，那么是一棵空树。
2、如果序列长度为 1，那么只有一个根节点。
3、如果长度大于 1，那么选取中间位置的数赋给根节点，然后前一半递归构建左子树，后一半递归构建右子树。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode *dfs(const vector<int> &nums, int left, int right) {
13         if (left > right) {
14             return nullptr;
15         }
16         int mid = (left + right) >> 1;
17         TreeNode *root = new TreeNode(nums[mid]); // 创建当前节点
18         root->left = dfs(nums, left, mid - 1); // 左子树填充值来自区间[left, mid - 1]
19         root->right = dfs(nums, mid + 1, right); // 右子树填充值来自区间[md + 1, right]
20         return root;
21     }
22     TreeNode* sortedArrayToBST(vector<int>& nums) {
23         return dfs(nums, 0, nums.size() - 1);
24     }
25 };