<Data Structures/Algorithms> leetcode hot100 - 128. Convert Sorted Array to Binary Search Tree

[LeetCode Hot 100] 128. Convert Sorted Array to Binary Search Tree

Problem Link

It’s natural to think of using recursion for this problem, which is also the standard approach to construct a binary search tree. Each time, we take the middle element of the current range as the root node and recursively find the left and right children in the left and right halves (i.e., the midpoints of the halves). The only thing to note is: what are we doing in each recursion? Answer: we find the current node and recursively construct its left and right children. As long as both children don’t exist, we could return, but it’s simpler to just go one layer deeper. If the current node doesn’t exist (i.e., left > right), it means we’ve reached a non-existent child, so we return null, which conveniently allows the parent to set the corresponding child pointer to null.

The complete code is as follows:

/**
 * 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);
    }
};

中文原文

[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);
    }
};