Convert sorted array to binary search tree

Question

I am working on "Convert a sorted array to a binary search tree with a minimum height", which asked:

Given a sorted array (order of magnification), convert it to create a binary tree with a minimum height.

I cannot find why my recursiveness does not stop as I expected. He should stop when 7 passes, and will not print 7 again. I also found a similar answer, it looks the same as mine, but it works fine. (I don’t think my question repeats itself, as these questions are listed above, but I still want to thank you to connect them for me. They gave me more ideas for solving my problem.)

My code is below:

public TreeNode sortedArrayToBST(int[] A) { int len = A.length; if(len <= 0){ return null; } TreeNode root = new TreeNode(A[(len - 1) / 2]); if(len == 1){ return root; } else{ helper(root, A, 0, len - 1); } return root; } public void helper(TreeNode root, int[] A, int leftPoint, int rightPoint){ if((rightPoint - leftPoint) <= 0){ return; } int mid = (rightPoint - leftPoint) / 2 + leftPoint; int leftChild = (mid - 1 - leftPoint) / 2 + leftPoint; int rightChild = (rightPoint - (mid + 1)) / 2 + mid + 1; TreeNode left = new TreeNode(A[leftChild]); root.left = left; TreeNode right = new TreeNode(A[rightChild]); root.right = right; helper(root.left, A, leftPoint, mid - 1); helper(root.right, A, mid + 1, rightPoint); return; } 

When I launched it, I got this.

My details
[1,2,3,4,5,6,7,8]

My conclusion
{4,2,6,1,3,5,7,#,#,#,#,#,#,7,8}

Expected
{4,2,6,1,3,5,7,#,#,#,#,#,#,#,8}

Why does he have duplicate 7 on the right side? Since 7 was used, it should be kicked out.

And I realized that my idea is similar to the following answer:

 public TreeNode sortedArrayToBST(int[] A) { // write your code here int len = A.length; if(len <= 0){ return null; } TreeNode root = helper1(A, 0, len - 1); return root; } public TreeNode helper1(int[] A, int low, int high){ if(low > high){ return null; } int mid = (high + low) / 2; TreeNode root = new TreeNode(A[mid]); root.left = helper1(A, low, mid - 1); root.right = helper1(A, mid + 1, high); return root; } 

Answer 1

Let there be the following array:

 [1,2,3,4,5,6,7] 

Expected BST:

  4 2 6 1 3 5 7 

To achieve this, we can go as follows:

 for (int i = 0; i < logn; i++) { //insert ith level } 

To simplify the problem, we find min n, therefore n > array.length and n = 2^k .

At level i, starting with i = 0 , we get:

n/2^(i+1), 3*n/2^(i+1), 5*n/2^(i+1)...

The numbers above are all the indices in the array.

 public TreeNode sortedArrayToBST(int[] A) { int len = A.length; if(len <= 0){ return null; } int n = 1; int i = 0; while (n < len) { n *= 2; i++; } TreeNode root = new TreeNode(A[n/2]); for (int j = 1; j < i; j++) { insert(root, j, n, A); } } private void insert(TreeNode root, int j, int n, int[] A) { int helper = n/Math.pow(2, j+1); for (int i = 1; i <= Math.pow(2, j); i ++) { root.add(A[i*helper]); } } 

Answer 2

It can work

 public TreeNode sortedArrayToBST(int[] A) { if (A.length() == 0) return null; return helper1(A, 0, A.length - 1); } public TreeNode helper1(int[] A, int low, int high) { if (low > high) return null; // Binary Search int mid = low + (high - low)/2; TreeNode root = new TreeNode(A[mid]); root.left = helper1(A, low, mid - 1); root.right = helper1(A, mid + 1, high); return root; }