LC669. 修剪二叉搜索树
相当于一个中序遍历吧，当某个节点<low时，其右子树的各个节点值虽然都比该节点值大，但仍可能存在<low的，所以要据于次节点，向其右子树进军遍历，等回溯时，delete掉该节点，返回的right要返回到上层递归，即该节点的父节点去接收这个right作为新的孩子节点。（奇怪的是，力扣中其实找到某个节点<low时，其左子数的每个节点包括其本身的指针都应该delete掉，奇怪的是我在编码时，提交了有delete root的版本，反而会报heap-use-after-free的错误）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
TreeNode* result = nullptr;
if (root == nullptr)
{
return nullptr;
}
if (root->val >= p->val && root->val <= q->val || root->val <= p->val && root->val >= q->val)
{
result = root;
}
if (root->val < p->val && root->val < q->val)
{
result = lowestCommonAncestor(root->right, p, q);
}
if (root->val > p->val && root->val > q->val)
{
result = lowestCommonAncestor(root->left, p, q);
}
return result;
}
LC108. 将有序数组转换为二叉搜索树
TreeNode* buildBST(vector<int>& nums, int left, int right)
{
if (left > right) //left==right就是传入的左右子树只剩一个节点时
{
return nullptr;
}
int mid = ((right - left) >> 1) + left;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums)
{
return buildBST(nums, 0, nums.size() - 1);
}
LC538. 把二叉搜索树转换为累加树
不知道累加树是哪种树，但根据例子观察的结果，其实就是包装好的一个右中左的中序遍历
TreeNode* prev = nullptr;
int sum = 0;
TreeNode* convertBST(TreeNode* root)
{
if(root == nullptr)
{
return nullptr;
}
root->right = convertBST(root->right);
sum += root->val;
root->val = sum;
root->left = convertBST(root->left);
return root;
}