DAY21|二叉树Part08|LeetCode: 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

目录

LeetCode: 669. 修剪二叉搜索树

基本思路

C++代码

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

基本思路

C++代码

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

基本思路

C++代码

---

LeetCode: 669. 修剪二叉搜索树

力扣代码链接

文字讲解：LeetCode: 669. 修剪二叉搜索树

视频讲解：你修剪的方式不对，我来给你纠正一下！

基本思路

        这个题目比较简单，但是一定要注意遇到节点在目标区间以外，不能直接返回null，而是应该继续向下判定，因为对于一个搜索二叉树来讲，在遍历整个二叉树的节点的过程中，如果某个节点的值小于区间的最小值，对于该节点的左子树中的所有节点一定都小于目标区间的最小值，但是右子树中却可能存在符合目标区间的值，因此还需要进一步进行判定。

• 确定递归函数的参数以及返回值

        参数：需要传入当前遍历的节点，还需要传入目标取件的边界值low和high。

        返回值：返回需要删除的节点。

TreeNode* trimBST(TreeNode* root, int low, int high)

• 确定终止条件

        修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了。

if (root == nullptr ) return nullptr;

• 确定单层递归的逻辑

        如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;
}

        如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;
}

        接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

C++代码

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr ) return nullptr;if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;}root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子return root;}
};

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

力扣代码链接

文字讲解：LeetCode: 108.将有序数组转换为二叉搜索树

视频讲解：构造平衡二叉搜索树！

基本思路

        构建平衡二叉树是为因为给定任意一个有序数组，都可以直接构建一颗线性结构的二叉树。而构建二叉树我们首先就应该想到根据数组构建二叉树，本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。分割点就是数组中间位置的节点。

• 确定递归函数返回值及其参数

        参数：需要传入一个有序数组，并且需要传入数组的左右下标（根据数组的左右下标来构建二叉树）

        返回值：返回构建二叉树的根节点。

// 左闭右闭区间[left, right]
TreeNode* traversal(vector<int>& nums, int left, int right)

        这里注意，我这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量原则。

• 确定递归终止条件

        这里定义的是左闭右闭的区间，所以当区间left>right当时候，就是空结点了。

if (left > right) return nullptr;

• 确定单层递归的逻辑

        根据数组区间的左右下标来构建二叉树，其中二叉树的根节点为mid = left+(right-left)/2,此时中间节点为：

TreeNode* root = new TreeNode(nums[mid]);

        接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点，最后返回root节点。

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;

C++代码

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

        注意：在调用traversal的时候传入的left和right为什么是0和nums.size() - 1，因为定义的区间为左闭右闭。

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

力扣代码链接

文字讲解：LeetCode: 538.把二叉搜索树转换为累加树

视频讲解：普大喜奔！二叉树章节已全部更完啦！

基本思路

        其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

        为什么变成数组就是感觉简单了呢？

        因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

• 递归函数参数以及返回值

        首先需要定义一个全局变量pre，用来记录前一个节点的值。

        参数：传入当前节点

        返回值：只需要对遍历的节点的值进行操作，不需要什么返回值。

int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)

• 确定终止条件

        遇空节点就终止。

if (cur == NULL) return;

• 确定单层递归的逻辑

        注意要右中左来遍历二叉树， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

traversal(cur->right);  // 右
cur->val += pre;        // 中
pre = cur->val;
traversal(cur->left);   // 左

C++代码

class Solution {
private:int pre = 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur == NULL) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};