701.二叉搜索树中的插入操作
题目描述
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5] 解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]
思路
本题如果考虑多种插入方式就会非常复杂，但是如果只考虑题目中的第一种插入方式，只将给出的数值插入到二叉树的最底下，也就是一直比较大小，遇到空节点的时候再插入，这道题目就会简单很多。
代码实现
/**
* 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* insertIntoBST(TreeNode* root, int val) {
TreeNode* node = new TreeNode(val);
if(root == NULL){
return node;
}
if(root->val>val){
root->left = insertIntoBST(root->left,val);
}
else root->right = insertIntoBST(root->right,val);
return root;
}
};108.将有序数组转换为二叉搜索树
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
思路
本题的本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。分割点就是数组中间位置的节点。
递归三部曲：
- 确定递归函数返回值及其参数
那么本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。
再来看参数，首先是传入数组，然后就是左下标left和右下标right，在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组。
// 左闭右闭区间[left, right]
TreeNode* traversal(vector<int>& nums, int left, int right)- 确定递归终止条件
这里定义的是左闭右闭的区间，所以当区间 left > right的时候，就是空节点了。
代码如下：
if (left > right) return nullptr;- 确定单层递归的逻辑
每次先构造当前节点，当前节点左边所有的值构成的数组，拿去构建左子树，右边的数组拿去构建右子树。
代码实现
/**
* 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* 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;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
return traversal(nums,left,right);
}
};538.把二叉搜索树转换为累加数
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
思路
递归三部曲：
- 递归函数参数以及返回值
这里我们使用双指针法，同时需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了。
代码如下：
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)- 确定终止条件
遇空就终止。
if (cur == NULL) return;
- 确定单层递归的逻辑
这里使用中序遍历，右中左的遍历顺序，中节点的处理逻辑是，将先前节点的数值与当前节点的数值相加，这里函数不需要返回相加的值，只需要遍历各个节点就行。
代码实现
/**
* 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:
int pre = 0;
void traversal(TreeNode* cur){
if(cur == NULL) return;
traversal(cur->right);
cur->val= cur->val + pre;
pre = cur->val;
traversal(cur->left);
}
TreeNode* convertBST(TreeNode* root) {
traversal(root);
return root;
}
};
