108. 将有序数组转换为二叉搜索树

发布时间：2020-12-14 04:22:00 所属栏目：大数据来源：网络整理

导读：Given an array where elements are sorted in ascending order,convert it to a height balanced BST. For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of? every ?node never differ

Given an array where elements are sorted in ascending order,convert it to a height balanced BST.

For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of?every?node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,5,9],One possible answer is: [0,9,-10,null,5],which represents the following height balanced BST:

      0
     /    -3   9
   /   /
 -10  5

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

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

示例:

给定有序数组: [-10,一个可能的答案是：[0,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     /    -3   9
   /   /
 -10  5

8ms

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     
13     int length=0;
14     TreeNode* theTree(vector<int>&vec,int left,int right)
15     {
16         if(right-left<=1)
17         {
18             return nullptr;
19         }
20         TreeNode *node=new TreeNode(vec[(left+right)/2]);
21         node->left=theTree(vec,left,(left+right)/2);
22         node->right=theTree(vec,(left+right)/2,right);
23         return node;
24     }
25     TreeNode* sortedArrayToBST(vector<int>& nums) {
26         
27         if(nums.size()==2)
28         {
29             TreeNode *q=new TreeNode(nums[0]);
30             q->right=new TreeNode(nums[1]);
31             return q;
32         }
33         if(nums.size()==1)
34         {
35             TreeNode *q=new TreeNode(nums[0]);
36             return q;
37         }
38         return theTree(nums,-1,nums.size());
39     }
40     
41 };static auto _=[]()
42     {
43         ios::sync_with_stdio(false);
44         cin.tie(0);
45         return 0;
46     }();

8ms

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x),right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* sortedArrayToBST(vector<int>& nums) {
13         if(nums.size()== 0) return NULL;
14         return helper(nums,0,nums.size()-1);
15     }
16     
17     TreeNode* helper(vector<int>& nums,int i,int j){
18         if(i>j) return NULL;
19         int index = i+(j-i)/2;
20         int mid= nums[index];
21         TreeNode* root = new TreeNode(mid);
22         root->left = helper(nums,i,index-1);
23         root->right = helper(nums,index+1,j);
24         return root;
25             
26         
27     }
28 };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!