首页 > 试题广场 >

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

[编程题]将升序数组转化为平衡二叉搜索树
  • 热度指数:32464 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个升序排序的数组,将其转化为平衡二叉搜索树(BST).

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值,右子树中所有节点的值都大于 node 的值,并且左右子树的节点数量之差不大于1

数据范围:,数组中每个值满足
进阶:空间复杂度 ,时间复杂度

例如当输入的升序数组为[-1,0,1,2]时,转化后的平衡二叉搜索树(BST)可以为{1,0,2,-1},如下图所示:
或为{0,-1,1,#,#,#,2},如下图所示:
返回任意一种即可。
示例1

输入

[-1,0,1,2]

输出

{1,0,2,-1}
示例2

输入

[]

输出

{}

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
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;
    }
};

发表于 2017-07-08 11:50:37 回复(2)

递归:

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;
        
    }
};

发表于 2022-03-15 18:40:45 回复(0)
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;
    }

发表于 2021-05-24 21:01:49 回复(0)
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;
    }

}

发表于 2020-04-30 10:28:07 回复(0)
/**
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;
    }
}

编辑于 2019-10-25 23:03:46 回复(0)
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;
    }
}

发表于 2019-06-21 14:24:40 回复(0)
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);
    }

发表于 2017-11-05 12:43:21 回复(2)
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;
	}
};

发表于 2017-08-31 02:25:30 回复(0)
/**
 * 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.length==0){
            
            return null;
        }
        

        return sortedArray(num,0,num.length-1);
        
        
    }
    
    
    public TreeNode sortedArray(int[] num,int left,int right) {
        
        if(left<0 || right>=num.length || left>right){
            return null;
        }
        
        int mid=(right+left)/2;
        
        if( (right-left)%2!=0 ){
            mid+=1;
        }
        
        TreeNode head=new TreeNode(num[mid]);
        
        head.left=sortedArray(num,left,mid-1);
        head.right=sortedArray(num,mid+1,right);
        
        return head;
        
        
        
        
        
    }

}
发表于 2017-08-19 14:50:27 回复(1)
/*递归思路: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;
    }
} 

发表于 2017-07-26 10:37:03 回复(1)
/**
 * 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;
	}
}

发表于 2017-07-02 17:00:42 回复(4)
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;
	}

}


发表于 2017-08-07 10:53:19 回复(8)
解题思路:
本题的解题主要采用分治+递归实现
因为所给数组为有序数组,题目要求得到一棵平衡二叉树
1.得到数组中间位置元素,此元素即为平衡查找树的根节点root
2.然后递归调用函数让数组前半段、后半段也为平衡查找树
3.root的左右子树分别为步骤2得到平衡查找树的根节点
4.返回root节点即为最后构建好的平衡二叉树

public class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
    if(nums==null || nums.length==0)
            return null;
        return help(nums,0,nums.length-1);
    }
    
    public TreeNode help(int[] num, int from, int to)
    {
    if(from<=to)
        {
            int mid = (from+to)/2; // int mid = (from+to)/2; leetcode通过
            TreeNode root = new TreeNode(num[mid]);
            root.left = help(num,from,mid-1);
            root.right = help(num,mid+1,to);
            return root;
        }
        return null;
    }
}
发表于 2016-08-15 18:26:05 回复(0)
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;
	}
}

发表于 2016-11-01 19:05:44 回复(2)
递归,简单易懂
import java.util.*;

public class Solution {

    public TreeNode sortedArrayToBST (int[] num) {
        int n = num.length;
        if (n == 0){
            return null;
        }
        int mid = n >> 1;
        TreeNode root = new TreeNode(num[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(num, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(num, mid + 1, n));
        return root;
    }
}


发表于 2022-01-21 13:42:48 回复(0)
public TreeNode sortedArrayToBST (int[] nums) {
    // write code here
    if(nums==null || nums.length==0){
        return null;
    }
    int len=nums.length ,mid=len/2;
    TreeNode root=new TreeNode(nums[mid]);
    root.left=sortedArrayToBST(Arrays.copyOfRange(nums ,0 ,mid));
    root.right=sortedArrayToBST(Arrays.copyOfRange(nums ,mid+1 ,len));
    return root;
}

编辑于 2024-03-17 15:16:12 回复(0)
/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    fn new_node(n: i32) -> Option<Box<TreeNode>> {
        Some(Box::new(TreeNode::new(n)))
    }
    fn binary_gen(nums: &Vec<i32>, left: i32, right: i32) -> Option<Box<TreeNode>> {
        if right < left {
            None
        } else {
            let mid = left + (right - left) / 2;
            let mut node = Self::new_node(nums[mid as usize]);
            node.as_mut()?.left = Self::binary_gen(nums, left, mid - 1);
            node.as_mut()?.right = Self::binary_gen(nums, mid + 1, right);
            node
        }
    }

    /**
    * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    *
    * 
        * @param nums int整型一维数组 
        * @return TreeNode类
    */
    pub fn sortedArrayToBST(&self, nums: Vec<i32>) -> Option<Box<TreeNode>> {
        // write code here
        Self::binary_gen(&nums, 0, nums.len() as i32 - 1)
    }
}

发表于 2023-09-03 20:04:00 回复(0)
dsdsd
发表于 2023-05-08 18:25:45 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param num int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here
        TreeNode tree = buildTree(num);
        return tree;
    }

    public static TreeNode buildTree(int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        if (arr.length == 1) {
            TreeNode node = new TreeNode(arr[0]);
            return node;
        }
        int rootIdx = arr.length / 2;
        TreeNode node = new TreeNode(arr[rootIdx]);
        int[] left = new int[rootIdx];
        System.arraycopy(arr, 0, left, 0, rootIdx);
        TreeNode leftNode = buildTree(left);
        node.left = leftNode;

        int[] right = new int[arr.length - rootIdx - 1];
        if (right.length > 0) {
            System.arraycopy(arr, rootIdx + 1, right, 0, (arr.length - rootIdx - 1));
            TreeNode rightNode = buildTree(right);
            node.right = rightNode;
        }
        return node;
    }
}

发表于 2023-04-25 15:18:04 回复(0)
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param num int整型一维数组 
  * @return TreeNode类
  */
function sortedArrayToBST( num ) {
    // write code here
    let numLen = num.length;
    if (numLen == 0) return null;
    let mid = parseInt(numLen/2);  
    let root = new TreeNode(num[mid]);
    let left1 = root, left2 = root, right1 = root, right2 = root;
    let left = mid - 1, right = mid + 1;
    while(left >= 0){
      left2 = new TreeNode(num[left]);
      left1.left = left2;
      left1 = left2;
      left--;
    }
    while(right <= numLen - 1){
      right2 = new TreeNode(num[right]);
      right1.right = right2;
      right1 = right2;
      right++;
    }
    return root;
}
module.exports = {
    sortedArrayToBST : sortedArrayToBST
};

发表于 2023-02-13 09:49:53 回复(0)