代码随想录算法训练营43期 | Day 21 —— 108.将有序数组转换为二叉搜索树、 538.把二叉搜索树转换为累加树

代码随想录算法训练营43期 | Day

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

class Solution {
private:TreeNode* traversal(vector<int>& nums, int left, int right) {if (left > right) return nullptr;int mid = left + ((right - left) / 2);TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid - 1);root->right = traversal(nums, mid + 1, right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = traversal(nums, 0, nums.size() - 1);return root;}
};

538.把二叉搜索树转换为累加树

class Solution {
public:int pre = 0;void traversal(TreeNode* cur){// 终止条件if(cur==nullptr) return;//右traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};