首页 计算机科学 算法 LeetCode

# 删除二叉搜索树中的节点

题目链接🔗

# 递归

  1. 确定递归函数参数和返回值

和在二叉搜索树中插入一样，也可以通过递归函数返回值删除节点。

  1. 确定终止条件

遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了。

  1. 确定单层递归的逻辑

有五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回 NULL 为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

删除二叉搜索树节点

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回 NULL 为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在 cur 的左孩子的位置
                TreeNode* tmp = root;   // 把 root 节点保存一下，下面来删除
                root = root->right;     // 返回旧 root 的右孩子作为新 root
                delete tmp;             // 释放节点内存（这里不写也可以，但 C++ 最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

# 修建二叉搜索树

题目链接🔗

下图中[1,3][1, 3] 区间在二叉搜索树中不单纯的由节点 3 和左孩子节点 0 来决定的，还要考虑节点 0 的右子树。

Alt text

要将节点 0 的右孩子节点 2，直接赋给节点 3，从而达到把节点 0 从二叉树中移除。

Alt text

# 递归

  1. 确定递归函数参数和返回值

因为要遍历整棵树做修改，有返回值，更方便，可以通过递归函数的返回值来移除节点。

  1. 确定终止条件

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

  1. 确定单层递归逻辑

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

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

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

最后返回 root 节点

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

# 迭代

因为二叉搜索树的有序性，不需要用栈来模拟递归。

修剪的时候分三步：

  • 将 root 移到[L,R][L, R] 范围内。
  • 修剪左子树
  • 修剪右子树
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;
        // 处理头结点，让 root 移动到 [L, R] 范围内，注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 小于 L 往右走
            else root = root->left; // 大于 R 往左走
        }
        TreeNode *cur = root;
        // 此时 root 已经在 [L, R] 范围内，处理左孩子元素小于 L 的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;
        // 此时 root 已经在 [L, R] 范围内，处理右孩子大于 R 的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};
# 将有序数组转化为二叉搜索树
题目链接🔗
如果根据数组构造一棵二叉树。本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
有序数组构造二叉搜索树，分割点就是数组中间位置的节点。
如果要分割的数组长度为偶数的时候，中间元素为两个，取哪一个都可以，只不过构成了不同的二叉搜索树。
  1. 确定递归函数的参数和返回值
本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。
参数，首先是传入数组，然后就是左下标 left 和右下标 right，，在构造二叉树的时候用下标来操作原数组。
  1. 确定递归终止条件
用左闭右闭区间，所以当左区间大于右区间的时候，就是空节点了。
  1. 确定单层递归逻辑
取数组中间元素位置要注意数组越界的问题，如果 left 和 right 都是 INT_MAX，就会越界。
可以写成intmid=left+((right−left)/2);int mid = left + ((right - left) / 2);
然后用中间元素构建节点，划分区间。
左孩子接往下一层左区间构造节点，右孩子接往下一层右区间构造节点。
最后返回 root。
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;
    }
};
# 把二叉搜索树转换为累加树
题目链接🔗
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
# 递归
本题依然需要一个 pre 指针记录当前遍历节点 cur 的前一个节点，这样才方便做累加。
  1. 确定递归函数参数和返回值
不需要递归函数的返回值做什么操作了，要遍历整棵树。
同时需要定义一个全局变量 pre，用来保存 cur 节点的前一个节点的数值，定义为 int 型就可以了。
  1. 确定递归终止条件
遇到空节点就返回.
  1. 确定单层递归的逻辑
要右中左来遍历二叉树， 中节点的处理逻辑就是让 cur 的数值加上前一个节点的数值。
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;
    }
};