CSharp solution with recursion


  • 0
    D
    public class Solution {
        public TreeNode SortedArrayToBST(int[] nums) {
            return ToBSTHelper(nums, 0, nums.Length -1);
        }
        
        TreeNode ToBSTHelper(int[] nums, int start, int end){
            if(start > end) return null;
            if(start == end) return new TreeNode(nums[start]);
            if(start == end -1){
                TreeNode root = new TreeNode(nums[start]);
                TreeNode right = new TreeNode(nums[end]);
                root.right = right;
                return root;
            }
            
            int middle = ((end - start)>>1) + start;
            TreeNode left = ToBSTHelper(nums, start, middle -1);
            TreeNode m_right = ToBSTHelper(nums, middle +1, end);
            TreeNode m_root = new TreeNode(nums[middle]);
            m_root.left = left;
            m_root.right = m_right;
            
            return m_root;
        }
    }

  • 0
    L

    a similar C# version.

    public TreeNode SortedArrayToBST(int[] nums) {
        return divideBuild(nums, 0, nums.Length - 1);
    }
    
    private TreeNode divideBuild(int[] nums, int left, int right){
        if(left == right) return new TreeNode(nums[left]);
        else if(left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = divideBuild(nums, left, mid - 1);
        root.right = divideBuild(nums, mid + 1, right);
        return root;
    }

  • 0
    D

    (left + right)/2 may cause overflow, the better way is (right - left)/2 + left


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.