代码随想录第二十一天 701.二叉搜索树中的插入操作 108.将有序数组转换为二叉搜索树

本文主要是介绍代码随想录第二十一天 701.二叉搜索树中的插入操作 108.将有序数组转换为二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;}
};

 

这篇关于代码随想录第二十一天 701.二叉搜索树中的插入操作 108.将有序数组转换为二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---