代码随想录算法训练营第 21天 |LeetCode669. 修剪二叉搜索树 LeetCode108.将有序数组转换为二叉搜索树 LeetCode 538.把二叉搜索树转换为累加树

代码随想录算法训练营

Day21 代码随想录算法训练营第 21天 |LeetCode669. 修剪二叉搜索树 LeetCode108.将有序数组转换为二叉搜索树 LeetCode 538.把二叉搜索树转换为累加树

---

---

前言

LeetCode669. 修剪二叉搜索树

讲解文档

LeetCode108.将有序数组转换为二叉搜索树

讲解文档

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

讲解文档

---

一、LeetCode669. 修剪二叉搜索树

1.题目链接

LeetCode 669. 修剪二叉搜索树

2.思路

（1）注意：删除节点是不可以直接将节点赋值为NULL
（2）递归思路：
1）遇到空节点：返回
2）当前节点root的值大于上限：

①右子树节点一定都大于上限，所以用左子结点顶替当前节点；
②左子结点是左子树递归调用函数的返回值，所以将左子树递归调用函数的返回值赋值给当前节点；
③当前节点已经确定，返回。

3）当前节点root的值小于下限：

①左子树节点一定都小于下限，所以用有子结点顶替当前节点
②右子结点是右子树递归调用函数的返回值，所以将右子树递归调用函数的返回值赋值给当前节点；
③当前节点已经确定，返回。

4）当前节点root的值在区间中：

节点不动，去确定节点的左右子节点。
右子结点是右子树递归调用函数的返回值，左子结点是左子树递归调用函数的返回值

3.题解

class Solution {
public:
    TreeNode* parent;
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL)
            return root;
        if (root->val > high) {
            root->right = NULL;
            root = trimBST(root->left, low, high);
            return root;
        }
        if (root->val < low) {
            root = trimBST(root->right, low, high);
            return root;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二、LeetCode108.将有序数组转换为二叉搜索树

1.题目链接

LeetCode108.将有序数组转换为二叉搜索树

2.思路

（1）平衡二叉搜索树：
1）平衡：子树高度差不超过1，所以根节点是最中间的节点
2）二叉搜索树：
中间节点左边的数组中所有数都小于中间节点，生成左子树；中间节点邮编的数组中所有数都大于中间节点，生成右子树
（2）递归
1）返回值：节点指针
参数：数组，闭区间左右端点
2）边界
l>r，区间无效，返回空
l==r，只有一个节点，返回刚刚制作的节点
3）单层递归
① 取出最中间的值：nums[(r - l) / 2 + l]，作为子树根节点
（这种写法可以防止超出int）
② 创建节点，作为子树的根节点
③ 如果l等于r，说明子树只有一个节点，返回
④节点的左子节点为左侧子数组递归调用返回值，节点的右子节点为右侧子数组递归调用返回值
⑤ 返回子树根节点

3.题解

class Solution {
public:
    TreeNode* build_BST(vector<int>& nums, int l,  int r) {
        if (l > r)
            return NULL;

        int val = nums[(r - l) / 2 + l];
        TreeNode* node = new TreeNode(val);
        if (l == r)
            return node;
        node->left = build_BST(nums, l, (l + r) / 2 - 1);
        node->right = build_BST(nums, (l + r) / 2 + 1, r);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        return build_BST(nums, 0, n - 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

1.题目链接

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

2.思路

（1）每个节点的新值（累加和）等于节点原值加右子节点新值：
因为右子节点是大于节点的最小节点，与右子节点相比，大于等于节点的数只多了节点自身的原值
（2）为什么从右向左求，而不是从左向右
1）最右侧的节点为最大节点，新值（累加和）就是原来的值，所以已知；
2）每个节点的新值（累加和）等于左子节点新值减去节点原值，理论上也可以从左向右，但是最左侧节点的累加和是所有节点原来值的总和，不易求

3.题解

class Solution {
public:
    int pre = 0;
    void in_order(TreeNode* node) {
        if (node == NULL)
            return;
        in_order(node->right);
        node->val += pre;
        pre = node->val;
        in_order(node->left);
    }

    TreeNode* convertBST(TreeNode* root) {
        if (root == NULL)
            return root;
        in_order(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

总结

1、对递归有了更深入的认识
（1）今天修建二叉树的递归相当于对子树进行修建，返回子树根节点
（2）在写递归的时候，将递归调用假想成已经实现的功能
（3）返回空还是节点指针

获取前中后序数组：返回空
增删节点：返回节点

其实有的时候一道题既可以返回空，也可以返回节点指针
2、二叉树题型总结
（1）二叉树的遍历：
1）深度优先：前序，中序，后序
2）广度优先：层序遍历
（2）二叉树的属性
1）深度：从根节点出发，经过多少节点-----前序
2）高度：从最底层出发，经过多少节点----后序
3）路径：前序
4）利用左右子节点的返回值求当前节点的属性-----后序
（3）二叉树的修改和构造
1）翻转
2）数组构造
3）合并
（4）二叉搜索树的属性：中序，利用有序性
（5）二叉搜索树的修改和构造
1）插入：递归搜索+节点插入（返回值为节点指针）
2）删除
3）修剪
4）构造平衡二叉搜索树
（6）公共祖先
1）二叉树最近公共祖先：后序，回溯（由于要对左右子节点进行判断，所以先进行左和右）
2）二叉搜索树最近公共祖先：第一个在区间内的
3、前中后序的选择

• 涉及到二叉树的构造，前序，先构造中节点
• 求普通二叉树的属性，一般是后序

后序一般是要通过递归函数的返回值做当前节点（中）计算
求深度也会用前序

• 求二叉搜索树的属性，中序（也可以是反转的中序）