Convert an ordered array to a binary search tree

LeetCode Chinese

LeetCode English

An ordered array in ascending order is transformed into a highly balanced binary search tree.

In this paper, a height balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.

Example:

Given an ordered array: [- 10, - 3,0,5,9],

A possible answer is: [0,-3,9,-10,null,5], which can represent the following highly balanced binary search tree:

      0
     / \
   -3   9
   /   /
 -10  5

Answer

In this paper, we investigate the properties of middle order building and balanced binary tree of binary tree, and use the properties of balanced binary search tree (balanced BST) to balance the array of middle order traversal node values of BST. its root node must be in the middle of the array. So this rule is also applicable to every subtree, which is the idea of recursion.

For the array composed of each subtree, there are the following situations:

1. Array is empty: when the empty node is reached, nullptr is returned directly;
2. Array is not empty: create a new node as the root node of the current subtree, whose value is taken as the value in the middle of the array, then use the sub array formed by the left part of the array to construct the left subtree, and use the sub array formed by the right part of the array to construct the right subtree.

C++ code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* getTree(vector<int>& vec,int l,int r)
    {
        if(l <= r)
        {
            int mid = l + (r - l) / 2;
            TreeNode* node = new TreeNode(vec[mid]);
            node->left = getTree(vec,l,mid - 1);
            node->right = getTree(vec,mid + 1,r);
            return node;
        }
        else
            return nullptr;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0)
            return nullptr;
        
        return getTree(nums,0,nums.size() - 1);
    }
};

Python code

# Definition for a binary tree node.
# class TreeNode:

#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recursion(self,nums: List[int],l: int,r: int) -> TreeNode:
        if l > r:
            return None
        m = (l + r) // 2
        node = TreeNode(nums[m])
        node.left = self.recursion(nums,l,m - 1)
        node.right = self.recursion(nums,m + 1,r)
        return node
    
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        n = len(nums)
        return self.recursion(nums,0,n - 1)