[leetcode108] convert an ordered array into a binary search tree (medium order traversal)

One 、 subject

Two 、 Ideas

Given ascending array , In fact, that is BST Traversal array in the middle order of , Just given a binary tree's middle order traversal array , It is not certain that a binary tree , But the problem requires a strictly balanced binary search tree , Therefore, you can select the middle element of the ascending sequence as the current root node element .

3、 ... and 、 Code

/** * 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* sortedArrayToBST(vector<int>& nums) {
    
        return dfs(nums, 0, nums.size() - 1);
    }
    TreeNode* dfs(vector<int>& nums, int left, int right){
    
        if(left > right){
    
            return nullptr;
        }
        // Take the middle element of the ascending array as the root node root
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};