将有序的数组转换为二叉搜索树
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: //找到中间的点作为新的根 TreeNode* add_note(vector<int>& nums , int left , int right ) { if (left > right) return nullptr; int mid = (left+right) /2 ; TreeNode *newnode = new TreeNode(nums[mid]); newnode->left = add_note(nums ,left , mid-1); newnode->right = add_note(nums , mid+1 , right); return newnode; } TreeNode* sortedArrayToBST(vector<int>& nums) { return add_note(nums , 0 ,nums.size()-1); } };
二刷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* track_back(vector<int>& nums,int left , int right) { if(right < left) return nullptr; int center = left + (right-left)/2; TreeNode* node = new TreeNode(nums[center]); cout<<nums[center]<<endl; node->left = track_back(nums , left ,center-1); node->right = track_back(nums , center+1 , right); return node; } TreeNode* sortedArrayToBST(vector<int>& nums) { return track_back(nums , 0 , nums.size()-1); } };
