Parallelize Convert Sorted Array to Binary Search Tree Function

Question

Я пытаюсь распараллелить мой преобразованный сортированный массив в программу BST на Java. Поскольку моя функция работает в режиме Divide и Conquer, я считаю, что она параллелизуема, но застряла в реализации. Это будет очень полезно, если вы, ребята, скажете мне, как подать темы здесь.

Заранее благодарен!

// Definition for a binary tree node. 
public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

public class Solution { 
    public TreeNode sortedArrayToBST(int[] nums) { 
     if (nums == null) { 
      return null; 
     } 
     return sortedArrayToBST(nums, 0, nums.length - 1); 
    } 

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) { 
     if (start > end) { 
      return null; 
     } 

     int mid = start + (end - start)/2; 
     TreeNode node = new TreeNode(nums[mid]); 
     node.left = sortedArrayToBST(nums, start, mid - 1); 
     node.right = sortedArrayToBST(nums, mid + 1, end); 

     return node; 
    } 
} 

Answer 1

Как предположил Андреас в комментариях, вы можете использовать forkjoinpool распараллелить творению бинарное дерево

class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

class Task extends RecursiveTask<TreeNode> 
{ 
    int[] nums; 
    int start,end; 
    public Task(int[] nums,int start,int end) 
    { 
     this.nums =nums; 
     this.start = start; 
     this.end = end; 
    } 
    protected TreeNode compute() 
    { 
     if(start>end) 
     { 
      return null; 
     } 
     int mid = start + (end - start)/2; 
     TreeNode node = new TreeNode(nums[mid]); 
     Task leftSubTask = new Task(nums,start,mid-1); 
     Task rightSubTask = new Task(nums,mid+1,end); 
     leftSubTask.fork(); 
     rightSubTask.fork(); 
     node.left = leftSubTask.join(); 
     node.right = rightSubTask.join(); 
     return node; 

    } 
} 
class Main 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     // your code goes here 
     int nums[] = {1,5,7,8,9}; 
     Task task = new Task(nums,0,nums.length-1); 
     ForkJoinPool forkJoinPool = new ForkJoinPool(4); 
     TreeNode root = forkJoinPool.invoke(task); 
    } 
}