C++算法学习心得五.二叉树（4）

1.二叉搜索树中的插入操作（701题）

题目描述：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

递归法：?只要遍历二叉搜索树，找到空节点 插入元素就可以了，有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        //节点为空，节点就是需要插入节点位置，并且把插入的节点返回
        if(root == NULL){
            TreeNode* node = new TreeNode(val);//新创建一个节点
            return node;//把这个节点返回
        }
        if(root->val > val)root->left = insertIntoBST(root->left,val);//根节点值大于目标值，左，根节点小于目标值，右
        if(root->val < val)root->right = insertIntoBST(root->right,val);
        return root;
    }
};

迭代法：使用了pre和cur两个指针的方法来实现迭代

class Solution {
public:
    //双指针的想法来实现，前一个节点和后一个节点来同时移动
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        TreeNode* pre = root;//记录上一个节点，对新的节点赋值操作
        TreeNode* cur = root;
        while(cur != NULL){
            pre = cur;
            if(cur->val > val)cur = cur->left;
            else cur = cur->right;
        }
        TreeNode* node = new TreeNode(val);
        if(val < pre->val) pre->left = node;//使用pre节点对其赋值
        else pre->right = node;
        return root;
    }
};

2.删除二叉搜索树中的节点（450题）

题目描述：

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

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

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为?$O(h)$，h 为树的高度。

递归法：需要考虑好根节点情况，判断要删除节点左右孩子情况，

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

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)return root;//没找到删除的节点，遇到空节点直接返回，
        //根节点的值等于目标值
        if(root->val == key){
            if(root->left == nullptr)return root->right;//左孩子为空，返回右节点
            else if(root->right == nullptr)return root->left;//右孩子为空返回左节点
            else{
                TreeNode* cur = root->right;//查找右子树上的最左面的节点
                //找最左面的节点
                while(cur->left!=nullptr){
                    cur = cur->left;
                }
                cur->left = root->left;//删除的节点左子树放在cur左子树上
                TreeNode* tmp = root;//保存root节点
                root = root->right;//返回右孩子作新的root节点
                delete tmp;//删除节点
                return root;
            }
        } 
        if(root->val > key)root->left = deleteNode(root->left,key);//左
        if(root->val < key)root->right = deleteNode(root->right,key);//右
        return root;
    }
};

普通二叉树的递归方式：

代码中目标节点（要删除的节点）被操作了两次：

• 第一次是和目标节点的右子树最左面节点交换。
• 第二次直接被NULL覆盖了。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

迭代法：

class Solution {
private:
    TreeNode* deleteNodeOperation(TreeNode* target){
        if(target == nullptr)return target;
        if(target->right == nullptr)return target->left;
        TreeNode* cur = target->right;
        while(cur->left){
            cur = cur->left;
        }
        cur->left = target->left;
        return target->right;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)return root;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(cur){
            if(cur->val == key)break;
            pre = cur;
            if(cur->val > key)cur = cur->left;
            else cur = cur->right;
        }
        if(pre == nullptr){
            return deleteNodeOperation(cur);
        }
        if(pre->left && pre->left->val == key){
            pre->left = deleteNodeOperation(cur);
        }
        if(pre->right && pre->right->val == key){
            pre->right = deleteNodeOperation(cur);
        }
        return root;
    }
};

因为二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整。主要难点在于如何处理左右节点都不为空情况

3.修剪二叉搜索树?（669题）

题目描述：

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

递归法：那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了（就是把节点0从二叉树中移除） ，上一个节点接收下面返回值直接返回

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);//寻找在区间内的节点，
            return right;
        }
        if(root->val > high){
            TreeNode* left = trimBST(root->left,low,high);//寻找区间内的节点
            return left;
        }
        root->left = trimBST(root->left,low,high);//左
        root->right = trimBST(root->right,low,high);//右
        return root;
    }
};

?迭代法：二叉搜索树，有序，不用栈去辅助就可实现

在剪枝的时候，可以分为三步：

• 将root移动到[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;
    }
};

4.将有序数组转换为二叉搜索树（108题）

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点?的左右两个子树的高度差的绝对值不超过 1。

递归法： 用数组的下标来操作数组，递归时候遵循循环不变量原则

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

迭代法：使用三个队列实现，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(0);   // 初始根节点
        queue<TreeNode*> nodeQue;           // 放遍历的节点
        queue<int> leftQue;                 // 保存左区间下标
        queue<int> rightQue;                // 保存右区间下标
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下标初始位置
        rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下标初始位置

        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front(); leftQue.pop();
            int right = rightQue.front(); rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
};

5.把二叉搜索树转换为累加树（538题）

题目描述：

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

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

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

?递归法：从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了

一个pre指针记录当前遍历节点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;
    }
};

迭代法：中序迭代的模版

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   // 右
            } else {
                cur = st.top();     // 中
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    // 左
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

总结：

二叉搜索树的插入操作：此题需要做的就是找到叶子节点然后再根据二叉搜索树的特性来，然后去接收左子树和右子树，向上返回，再根据二叉搜索树的特性来完成实现，根据值来遍历，迭代法使用两个节点的方法来实现，

删除二叉搜索树中的节点：这里要考虑递归法的终止条件设定，考虑好左右子树是否为空的几种情况，再对这些情况做出相应的处理，主要注意左右子树不为空的情况如何去处理，需要在右子树的最左子树的节点去将左子树接收，然后把值去掉接收右子树即可，迭代法去实现

修剪二叉搜索树：利用了删除二叉搜索树的方法来实现，就是需要将减枝下来的节点去接收，然后再进行迭代，注意二叉搜索树是根据值来递归的，因为其值有大小有序，所以可以按照这个方向，来进行递归，

将有序数组转换成二叉搜索树：将一个数组按照中间数据进行分割，然后再进行左数组和右数组进行分别来进行递归，按照取中间节点操作进行，然后按照节点值来进行递归，最好按照数组的下标来进行操作就好了，

把二叉搜索树转换为累加树：累加树来进行数值的反中序遍历，先进行右遍历，然后处理中间节点的操作，之后再进行左处理，注需要使用整形的数来接收前一个节点的值，来实现，其实和双指针的想法差不多