/** * 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* trimBST(TreeNode* root, int low, int high) { if(!root) return nullptr; if(root->val < low) return trimBST(root->right, low, high); if(root->val > high) return trimBST(root->left, low, high); root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子 root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子 return root; } };
/** * 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* search(vector<int> nums, int left, int right){ if(left>right) return nullptr; int mid = (right + left)/2; TreeNode* node = new TreeNode(nums[mid]); node->left = search(nums, left, mid-1); node->right = search(nums, mid+1, right); return node; } TreeNode* sortedArrayToBST(vector<int>& nums) { return search(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* pre = NULL; TreeNode* convertBST(TreeNode* root) { if(!root) return nullptr; root->right = convertBST(root->right); if(pre) root->val += pre->val; pre = root; root->left = convertBST(root->left); return root; } };