The title information

Subject address: leetcode-cn.com/problems/co…

Converts an ordered array in ascending order into a highly balanced binary search tree.

In this case, a highly 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 is less than 1.

Example:

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

One possible answer is: [0,-3,9,-10, NULL,5], which could represent the following highly balanced binary search tree:

      0
     / \
   -3   9
   /   /
 -10  5
Copy the code

Solution: Recursion (middle order)

An ascending array, turn binary tree or search tree (right subtree and left subtree), so the array is equivalent to a middle-order traversal of the search tree

For the example array: [-10,-3,0,5,9], there are many binary search tree results

Such as:

      0
     / \
   -3   5
   /     \
 -10      9 
Copy the code
      5
     / \
   -3   9
   / \    
 -10  0    
Copy the code

The current problem is to find a highly balanced solution (so the above solution is not satisfied with equilibrium), so try to take the middle root, is the most balanced.

If it’s even, take any of the middle two. As follows either -10 is the current root -3 is its left child, or -3 is the current root -10 is its right child

So we can derive recursion

public TreeNode sortedArrayToBST(int[] nums) {
    return recurrence(nums, 0, nums.length - 1);
}
/ / to take root
public TreeNode recurrence(int[] nums, int left, int right) {
    if (left > right) return null;
    // The division operation is rounded down, so the even number is on the left
    int mid = (left + right) / 2;
    // get to the root node
    TreeNode root = new TreeNode(nums[mid]);
    // Select the root from the left and right trees
    root.left = recurrence(nums, left, mid - 1);
    root.right = recurrence(nums, mid + 1, right);
    return root;
}
Copy the code

The time, of course, is order n, and the balance is that the depth of the stack is log2n so the space is order logn.

conclusion

In general, it’s a dichotomous thing, and the problem is to find a solution that satisfies this condition

int mid = (left + right) / 2;
Copy the code

So what you get is if you take the left-hand side of an even number, if you add a 1 and then divide by 2 you take the right side, or if you add a random number (0/1). So each time you do that you might get a different tree that satisfies the condition.

Finally, the chapter on trees in the primary collection is over and the chapter on data structures in this collection is over. From the beginning, I was unfamiliar with structures like trees, and just traversal operations are very different from linear data structures, but now I am more familiar with such a data structure even though I have only 5 questions. Starting with the next chapter is a chapter on algorithmic thinking directions (sorting, dynamic programming, mathematics, etc.)