ch7-of-programmercarl-3

C++ C 代码随想录二叉树 DFS BFS 二叉搜索树

刷题

发布日期: 2022-04-19

701.二叉搜索树中的插入操作
- 思路
- 代码
450.删除二叉搜索树中的节点
- 思路
- 代码
669. 修剪二叉搜索树
- 思路
- 代码
108.将有序数组转换为二叉搜索树
- 思路
- 代码
538.把二叉搜索树转换为累加树
- 思路
- 代码
总结

1 二叉搜索树中的插入操作

题目链接：701. 二叉搜索树中的插入操作

1.1 题目描述

给定二叉搜索树（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]

1.2 思路

BST插入结点只需要按照BST的性质寻找插入位置即可。

当待插入的树为空树时，直接将待插入节点作为根节点返回即可。
当待插入的树不为空时，按照BST性质查找位置：
- 当待插入节点的值小于当前节点值时，则插入位置在当前节点的左子树中。
- 当待插入节点的值大于当前节点值时，则插入位置在当前节点的右子树中。
- 当待插入节点的值等于当前节点值时，插入失败。

完整代码如下：

Cpp 实现

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            return new TreeNode(val);
        }

        TreeNode *cur = root;
        while(cur){
            if(cur->val < val){
                if(!cur->right){
                    cur->right = new TreeNode(val);
                    return root;
                }
                cur = cur->right;
            }else if(cur->val > val){
                if(!cur->left){
                    cur->left = new TreeNode(val);
                    return root;
                }
                cur = cur->left;
            }
        }
        return root;
    }
};

C 实现

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    struct TreeNode *cur = root;
    struct TreeNode* node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    if(!cur){
        return node;
    }
    while(cur){
        if(cur->val > val){
            if(!cur->left){
                cur->left = node;
                return root;
            }
            cur = cur->left;
        }else{
            if(!cur->right){
                cur->right = node;
                return root;
            }
            cur = cur->right;
        }
    }
    return root;
}

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

题目链接：450. 删除二叉搜索树中的节点

2.1 题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例1:

输入: root = [5,3,6,2,4,null,7], key = 3
输出: [5,4,6,2,null,null,7]
解释: 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例3:

输入: root = [], key = 0
输出: []

2.2 思路

二叉树删除操作相对插入操作较为复杂。首先需要查找待删除节点位置，如果节点不在树中，则返回false表明删除失败即可。当找到待插入节点的位置时，有以下三种情况：

待删除结点的左子树为空：将该节点的双亲结点指向其的指针改为指向其右子树，然后将该节点释放即可。
待删除结点的右子树为空：将该节点的双亲结点指向其的指针改为指向其左子树，然后将该节点释放即可。
待删除结点的左右子树均不为空：将该节点的值修改为其左子树中最大值或右子树中最小值，并将对应的结点删去即可。

完整代码如下：

Cpp实现

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return root;

        TreeNode *cur = root, *parent = NULL;
        while(cur){
            if(cur->val > key){
                parent = cur;
                cur = cur->left;
            }else if(cur->val < key){
                parent = cur;
                cur = cur->right;
            }else{
                break;
            }
        }
        if(!cur) return root;
        if(!cur->left){
            if(!parent){              //当这个条件满足时说明删去的是根节点
                return cur->right;
            }else if(parent->val < key){
                parent->right = cur->right;
            }else{
                parent->left = cur->right;
            }
        }else if(!cur->right){
            if(!parent){              //当这个条件满足时说明删去的是根节点
                return cur->left;
            }else if(parent->val < key){
                parent->right = cur->left;
            }else{
                parent->left = cur->left;
            }
        }else{
            TreeNode *cur1 = cur->right; 
            parent = cur;
            while(cur1->left){          //找右侧最小值
                parent = cur1;
                cur1 = cur1->left;
            }
            cur->val = cur1->val;       //将待删除结点的值改为右侧最小
            if(parent->right == cur1){  //说明待删除结点右侧最小即为其右孩子
                parent->right = cur1->right;
            }else{
                parent->left = cur1->right;
            }
            delete(cur1);
        }
        return root;
    }       
};

C实现

struct TreeNode* deleteNode(struct TreeNode* root, int key){
    if(!root) return root;

    struct TreeNode *cur = root, *parent = NULL;
    while(cur){
        if(cur->val > key){
            parent = cur;
            cur = cur->left;
        }else if(cur->val < key){
            parent = cur;
            cur = cur->right;
        }else{
            break;
        }
    }
    if(!cur) return root;
    if(!cur->left){
        if(!parent){              //当这个条件满足时说明删去的是根节点
            return cur->right;
        }else if(parent->val < key){
            parent->right = cur->right;
        }else{
            parent->left = cur->right;
        }
    }else if(!cur->right){
        if(!parent){              //当这个条件满足时说明删去的是根节点
            return cur->left;
        }else if(parent->val < key){
            parent->right = cur->left;
        }else{
            parent->left = cur->left;
        }
    }else{
        struct TreeNode *cur1 = cur->right; 
        parent = cur;
        while(cur1->left){          //找右侧最小值
            parent = cur1;
            cur1 = cur1->left;
        }
        cur->val = cur1->val;       //将待删除结点的值改为右侧最小
        if(parent->right == cur1){  //说明待删除结点右侧最小即为其右孩子
            parent->right = cur1->right;
        }else{
            parent->left = cur1->right;
        }
        free(cur1);
    }
    return root;
}

3 修剪二叉搜索树

题目链接：669. 修剪二叉搜索树

3.1 题目描述

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例1:

输入: root = [1,0,2], low = 1, high = 2
输出: [1,null,2]

示例2:

输入: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出: [3,2,null,1]

3.2 思路

递归：当根节点值小于low则递归其右子树，若大于high则递归其左子树，否则分别在左右子树中寻找，并将下一层的递归结果返回给当前结点的左右孩子。

完整代码如下：

Cpp 实现

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root)   return nullptr;
        if(root->val < low)     return trimBST(root->right, low, high); //递归右子树
        if(root->val > high)    return trimBST(root->left, low, high);  //递归左子树
        root->left = trimBST(root->left, low, high);  //重连左孩子
        root->right = trimBST(root->right, low, high);  //重连右孩子
        return root;
    }
};

迭代：
- 首先先把根节点root移动到目标范围中，然后分别对左、右子树进行修剪。
- 由于第一步我们已经把root移动到目标范围中,那么小于low的只会在左子树中出现。遍历左子树，当所遍历的结点的左孩子的值小于low，则该节点的左孩子及其左子树都将小于low，因而应该在该节点的左孩子的右子树中寻找，即将当前结点的左孩子连到原来的左孩子的右孩子:cur->left = cur->left->right直至访问的结点为空。
- 第二步完成了左子树的修剪，右子树的修剪也是类似的。对右子树进行遍历，当当前的结点的右孩子的值大于high，说明该节点的右孩子及其右子树的值都大于high，因而我们需要在该节点的右孩子的左子树中寻找符合要求的结点，因此：cur->right = cur->right->left.
Cpp 实现

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        //下边第一种写法最后可能会导致root->val > high
        /*while(root && root->val > high){
            root = root->left;
        }
        while(root && root->val < low){
            root = root->right;
        }*/
        
        //将根节点移动到目标范围内
        while(root && (root->val < low || root->val > high)){
            if(root->val < low) root = root->right;
            else root = root->left;
        }
        if(!root) return nullptr; //移动后如果根节点为空则说明整棵树都不在范围内
        TreeNode* cur = root;
        while(cur){
            while(cur->left && cur->left->val < low){
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;
        while(cur){
            while(cur->right && cur->right->val > high){
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

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

题目链接：108. 将有序数组转换为二叉搜索树

4.1 题目描述

给你一个整数数组 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]

4.2 思路

取数组中间那个值为根节点，然后左右两侧各为左右子树进行构建即可。

完整代码如下：

Cpp 实现

class Solution {
public:
    TreeNode* construct(vector<int> nums, int l, int r){
        if(l > r){
            return nullptr;
        }
        int m = l + (r - l) / 2;
        TreeNode *node = new TreeNode(nums[m]);
        node->left = construct(nums, l, m - 1);
        node->right = construct(nums, m + 1, r);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return construct(nums, 0, nums.size()-1);
    }
};

C 实现

struct TreeNode* addNode(int *nums, int left, int right){
    if(left > right) return NULL;
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    int mid = (left + right) / 2;
    root->val = nums[mid];
    root->left = addNode(nums, left, mid - 1);
    root->right = addNode(nums, mid + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    struct TreeNode* root = addNode(nums, 0, numsSize - 1);
    return root;
}

5 把二叉搜索树转换为累加树

题目链接：538. 把二叉搜索树转换为累加树

5.1 题目描述

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例1:

输入: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例2:

输入: root = [0,null,1]
输出: [1,null,1]

示例3:

输入: root = [1,0,2]
输出: [3,3,2]

示例4:

输入: root = [3,2,4,1]
输出: [7,9,4,10]

5.2 思路

其实就是树的遍历罢了，只是要创建一个变量用于存储上一个访问的结点的值，然后将其加到当前结点上，并更新该变量即可。遍历顺序就是中序遍历的镜像，即“右-根-左”.

完整代码如下：

Cpp实现

class Solution {
public:
    void traverse(TreeNode* root){
        if(!root) return;

        stack<TreeNode*> s;
        s.emplace(root);
        int val = 0;
        while(!s.empty()){
            TreeNode* cur = s.top();
            s.pop();
            if(cur){
                if(cur->left) s.emplace(cur->left);
                s.emplace(cur);
                s.emplace(nullptr);
                if(cur->right) s.emplace(cur->right);
            }else{
                cur = s.top();
                s.pop();
                cur->val += val;
                val = cur->val;
            }
        }
    }
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }
};

C实现

struct TreeNode* convertBST(struct TreeNode* root){
    if(!root) return root;
    int sum = 0;
    struct TreeNode *stack[10001];
    int stack_top = 0;
    stack[stack_top++] =root;
    while(stack_top != 0){
        struct TreeNode *cur = stack[--stack_top];
        if(cur){
            if(cur->left) stack[stack_top++] = cur->left;
            stack[stack_top++] = cur;
            stack[stack_top++] = NULL;
            if(cur->right) stack[stack_top++] = cur->right;
        }else{
            cur = stack[--stack_top];
            cur->val += sum;
            sum = cur->val;
        }
    }
    return root;
}