将升序数组转化为平衡二叉搜索树

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) 
    {
        return ArrayToBST(num,0,num.size());
    }
    TreeNode *ArrayToBST(vector<int> &num,int begin,int end)
    {
        if(begin >= end)
            return nullptr;
        int middle = (end+begin)>>1;
        TreeNode *root = new TreeNode(num[middle]);
        root->left = ArrayToBST(num,begin,middle);
        root->right = ArrayToBST(num,middle+1,end);
        return root;
    }
};

递归：

1） 先定义一个遍历函数 参数是一个数组nums 一个左left一个右right标记数组区间 返回值是一个节点TreeNode* traversal(vector<int> &num,int left,int right)

2） 先判断 left>right  则返回空  求出一个中点位置

if(left>right)return nullptr;int mid =left+(right-left)/2;

3） New一个值为数组中点值的节点当作根节点

TreeNode* root =new TreeNode(num[mid]);

4） 递归 得到根节点的左root->left =traversal(num, left, mid-1);

5） 递归得到根节点的右 root->right=traversal(num,mid+1,right);

6） 返回根节点return root;

7） 进入 构造平衡二叉搜索树的函数 调用递归函数  

TreeNode* root =traversal(num, 0, num.size()-1);return root;

class Solution {
public:
    /**
     * 
     * @param num int整型vector 
     * @return TreeNode类
     */
    TreeNode* traversal(vector<int> &num,int left,int right){
        if(left>right)return nullptr;
        int mid =left+(right-left)/2;
        TreeNode* root =new TreeNode(num[mid]);
        root->left =traversal(num, left, mid-1);
        root->right=traversal(num,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& num) {
        // write code here
        TreeNode* root =traversal(num, 0, num.size()-1);
        return root;
        
    }
};

public TreeNode sortedArrayToBST (int[] num) {
        if (num == null || num.length == 0) {
            return null;
        }
        
        return helper(num, 0, num.length - 1);
    }
    
    private TreeNode helper(int[] num, int left, int right) {
        if (left > right) {
            return null;
        }
        
        int mid = (right - left + 1) / 2 + left;
        TreeNode root = new TreeNode(num[mid]);
        root.left = helper(num, left, mid - 1);
        root.right = helper(num, mid + 1, right);
        return root;
    }

public class Solution22 {
	public TreeNode sortedArrayToBST(int[] num) {
        if(num==null||num.length==0)
        	return null;
        return sorted(num,0,num.length-1);
    }
    
    public TreeNode sorted(int[] num,int left,int right) {
    	 if(left>right)
    		 return null;
       	 int mid =(left+right+1)/2;
    	 int num1 =num[mid];
    	 TreeNode node = new TreeNode(num1);
    	 node.left =sorted(num,left,mid-1);
    	 node.right = sorted(num,mid+1,right);
    	 return node;
    }

}

/**
Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 38 MB, less than 25.77% of Java online submissions for Convert Sorted Array to Binary Search Tree.
*/
public class Solution {
    
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) {
            return null;
        }
        return process(num, 0, num.length - 1);
    }
    
    public TreeNode process(int[] num, int start, int end) {
        if (start > end) {
            return null;
        }
        int k = end - start + 1;
        int mid;
        if (k % 2 == 0) {
            mid = start + (end - start) / 2 + 1;
        } else {
            mid = start + (end - start) / 2;
        }
        TreeNode root = new TreeNode(num[mid]);
        root.left = process(num, start, mid - 1);
        root.right = process(num, mid + 1, end);
        return root;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num.length==0)
            return null;
        int start=0;
        int end=num.length;
        //注意边界问题 
        //end取不到
        return toBST(num,start,end);
    }
    private TreeNode toBST(int[] num,int start,int end){
        if(start==end)
            return null;
        int mid =(start+end)/2;
        TreeNode root =new TreeNode(num[mid]);
        root.left=toBST(num,start,mid);
        root.right=toBST(num,mid+1,end);
        return root;
    }
}

TreeNode *bst(vector<int> &num,int start,int end){
        if(end<start)
            return NULL;
        if(end==start){
            TreeNode *p=new TreeNode(num[start]);
            return p;
        }
        int mid=(start+end+1)/2;
        TreeNode *root=new TreeNode(num[mid]);
        root->left=bst(num,start,mid-1);
        root->right=bst(num,mid+1,end);
        return root;
    }
    
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return bst(num,0,num.size()-1);
    }

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return ArrayToBST(num,0,num.size());
    }
    TreeNode *ArrayToBST(vector<int> &num,int begin,int end)
    {
    	if(begin >= end)
    		return NULL;
    	int mid = (begin+end)>>1;
    	TreeNode *root = new TreeNode(num[mid]);
    	root->left = ArrayToBST(num,begin,mid);
    	root->right = ArrayToBST(num,mid+1,end);
    	return root;
	}
};

/*递归思路：1.f(p,end)找到链表（起始p,到终止end）中最中间的节点，作为根节点,并返回。
           2.这个节点的left=f(p,中间节点)
           3.这个节点的right=f(中间节点.next，end)
*/      
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
       return  f(head,null);
    }
    public TreeNode f(ListNode p,ListNode end){
         if(p==null||p==end) return null;
         if(p.next==end) return new TreeNode(p.val);
        ListNode slow=p;
        ListNode fast=p;
        while(fast.next!=end && fast.next.next!=end){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(fast.next!=end) //边界值处理
        slow=slow.next;
        TreeNode root  = new TreeNode(slow.val);
        root.left=f(p,slow);
        root.right=f(slow.next,end);
        return root;
    }
} 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num == null || num.length == 0)
        	return null;
        
        return createTree(num, 0, num.length - 1);
    }
	
	public TreeNode createTree(int[] num, int begin, int end){
		if(begin > end)
			return null;
		// 确定根的索引，这里一定要+1！
		int inx = (end + begin + 1) / 2;
		TreeNode root = new TreeNode(num[inx]);
		root.left = createTree(num, begin, inx - 1);
		root.right = createTree(num, inx + 1, end);
		return root;
	}
}

package go.jacob.day807;

/**
 * 108. Convert Sorted Array to Binary Search Tree
 * @author Jacob
 * 这道题是二分查找树的题目，要把一个有序数组转换成一颗二分查找树。
 * 从本质来看，如果把一个数组看成一棵树（也就是以中点为根，左右为左右子树，依次下去）
 * 数组就等价于一个二分查找树。
 * 所以如果要构造这棵树，那就是把中间元素转化为根，然后递归构造左右子树。
 * 所以我们还是用二叉树递归的方法来实现，以根作为返回值，每层递归函数取中间元素，
 * 作为当前根和赋上结点值，然后左右结点接上左右区间的递归函数返回值。
 * \时间复杂度还是一次树遍历O(n)，
 * 总的空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。 
 */
public class Demo3 {
	public TreeNode sortedArrayToBST(int[] nums) {
		if(nums==null||nums.length==0)
			return null;
		return sortedArrayToBST(nums,0,nums.length-1);
	}

	private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
		if(right<left)
			return null;
		if(left==right)
			return new TreeNode(nums[left]);
		int mid=left+(right-left+1)/2;
		TreeNode root=new TreeNode(nums[mid]);
		
		root.left=sortedArrayToBST(nums,left,mid-1);
		root.right=sortedArrayToBST(nums,mid+1,right);
		
		return root;
	}

}

public class Solution {
   public TreeNode sortedArrayToBST(int[] num) {
		if(num == null || num.length == 0) return null;
		return createTree(num, 0, num.length - 1);
	}
	public static TreeNode createTree(int[] num, int start, int end) {
		if(start > end) return null;
		int mid = (start + end) / 2 + (start + end) % 2;
		TreeNode root = new TreeNode(num[mid]);
		root.left = createTree(num, start, mid - 1);
		root.right = createTree(num, mid + 1, end);
		return root;
	}
}

public TreeNode sortedArrayToBST (int[] nums) {
    // write code here
    if(nums.length==0){
        return null;
    }
    int mid=nums.length/2;
    TreeNode root=new TreeNode(nums[mid]);
    root.left=sortedArrayToBST(Arrays.copyOfRange(nums ,0 ,mid));
    root.right=sortedArrayToBST(Arrays.copyOfRange(nums ,mid+1 ,nums.length));
    return root;
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return buildBST(nums, 0, nums.length - 1);
    }
    /**
    * 递归构建平衡二叉搜索树
    * @param nums 有序数组
    * @param left 当前处理的左边界
    * @param right 当前处理的右边界
    * @return 当前子树的根节点
    */
    private TreeNode buildBST(int[] nums, int left, int right) {
        // 递归终止条件
        if (left > right) {
            return null;
        }

        // 选择中间位置作为根节点
        // 使用 (left + right) >>> 1 避免整数溢出
        int mid = (left + right) >>> 1;

        // 创建根节点
        TreeNode root = new TreeNode(nums[mid]);

        // 递归构建左子树和右子树
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);

        return root;
    }
}

class Solution:
    def sortedArrayToBST(self , nums: List[int]):
        # write code here
        n = len(nums)
        if n == 0: return None
        k = n//2
        node = TreeNode(nums[k])
        if n == 1 : return TreeNode(nums[0])
        node.left = self.sortedArrayToBST(nums[:k])
        node.right = self.sortedArrayToBST(nums[k+1:])
        return node
问题的核心就是：找到父节点，然后左右两边再递归