Java recursion method, find mid to create middle node


  • 0
    K
    /**
     * 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 convert(0, nums.length-1, nums);
        }
        
    // kinds of binary search
        private TreeNode convert(int min, int max, int[] nums) {
            if(min > max || max < min) {
                return null;
            }
            int mid = (min + max) /2; //-> need to care for int overflow
            TreeNode root = new TreeNode(nums[mid]);
            root.left = convert(min, mid-1 , nums); // we already construct mid node, so we avoid mid 
            root.right = convert(mid+1, max, nums);
            return root;
        }
    }
    

  • 0
    K

    update :
    for avoid overflow, change

    int mid = (min + max) /2 
    

    to be

    int mid = min + (max - min) /2 ; //-> avoid overflow
    

Log in to reply
 

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