LeetCode之将有序数组转换为二叉搜索树（一百零八）

目录

题目

解题

方法一、中序遍历

题目

（原题链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/）

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

解题

方法一、中序遍历

分析： 二叉搜索树的中序遍历是升序排列的，题目给定的数组是按照升序排序的有序数组，因此可以确定数组是某二叉搜索树的中序遍历序列。以数组中中间位置的元素为根结点，采用循环递归左右子树的方式构建高度平衡的二叉搜索树。

代码：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 TreeNode* helper(vector<int>& nums, int left, int right) {
     
    
   

    

     

    
    

     
 if (left > right) {
     
    
   

    

     

    
    

     
 return nullptr;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 总是选择中间位置右边的数字作为根节点
     
    
   

    

     

    
    

     
 int mid = (left + right + 1) / 2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       root->left = helper(nums, left, mid - 1);
     
    
   

    

     

    
    

     

       root->right = helper(nums, mid + 1, right);
     
    
   

    

     

    
    

     
 return root;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 TreeNode* sortedArrayToBST(vector<int>& nums) {
     
    
   

    

     

    
    

     
 return helper(nums, 0, nums.size() - 1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107098922