<数据结构/算法> leetcode hot100系列. 128. 将有序数组转化为二叉搜索树

[LeetCode hot 100] 128. 将有序数组转化为二叉搜索树

题目链接

这个题很自然地想到要用递归，这也是构建二叉搜索树的标准步骤。每次都从当前的区间取中点作为根节点，并且分别在左右半区内寻找左孩子和右孩子（即左右半区的中点），如此递归。唯一需要注意的是我们在每次递归中都在做些什么？答：我们找到当前的节点，并调用递归来构造当前节点的左右孩子节点。只要左右孩子都没有就可以返回了，但是这样判断起来太麻烦，不如直接再往深了走一层，假如当前节点不存在(即left > right)，就说明走到了不存在的孩子那一层，返回null即可，正好方便父节点把对应孩子的指针设为null。

完整代码如下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    TreeNode* recur(vector<int>& nums, int left, int right){
        if(left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* cur = new TreeNode(nums[mid]);
        cur->left = recur(nums, left, mid - 1);
        cur->right = recur(nums, mid + 1, right);
        return cur;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        return recur(nums, left, right);
    }
};