代码随想录算法训练营Day22|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

目录

235. 二叉搜索树的最近公共祖先

前言

递归法

迭代法

701.二叉搜索树中的插入操作

前言

递归法

450.删除二叉搜索树中的节点

前言

递归法

总结

---

235. 二叉搜索树的最近公共祖先

题目链接

文章链接

前言

? ? ? ? ?前一题求解二叉树的最近公共祖先，是利用回溯自底向上搜索，遇到一个节点的左子树里有p，右子树里有q，就表明当前节点是最近公共祖先。

? ? ? ? 若是对二叉搜索树进行两节点最近公共祖先查找，可以利用二叉搜索树的结构特点，p和q的最近公共祖先一定满足介于[p,q]区间内的条件，基于此可以分别进行判断搜索。

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){
        if (cur == NULL) return cur;
        
        if (cur->val > p->val && cur->val > q->val){
            TreeNode* left = traversal(cur->left, p, q); //递归函数有返回值，用left接收
            if (left != NULL){
                return left;
            }
        }
        
        if (cur->val < p->val && cur->val < q->val){
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL){
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

? ? ? ? 递归法主要是对三种情况进行判断，在判断中进行递归遍历。

迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root){
            if (root->val > p->val && root->val > q->val){
                root = root->left;
            }
            else if (root->val < p->val && root->val < q->val){
                root = root->right;
            }
            else{
                return root;
            }
        }
        return NULL;
    }
};

? ? ? ? 迭代法的思路与递归法类似，实现上更为简便。

701.二叉搜索树中的插入操作

题目链接

文章链接

前言

? ? ? ? ?由于是对二叉搜索树进行插入操作，并且插入的新值和二叉搜索树任意节点值都不同，因此只要寻找到合适的叶子节点进行插入操作即可。

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};

? ? ? ? 根据节点值和插入值的大小判断想左和向右进行遍历，直到遍历到最后一个叶子节点。本题的重点在于学习如何通过递归函数返回值完成新加入节点的父子关系赋值操作。当遍历到叶子节点时，下层将加入节点返回，本层用root->left或者root->right接收。

450.删除二叉搜索树中的节点

题目链接

文章链接

前言

? ? ? ? ?与上一题二叉搜索树的插入操作相比，对于二叉搜索树的删除操作就显得较为复杂了，因为不单单是对叶子节点的操作，需要考虑多种可能以及各种可能对应的删除节点的实现操作。

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //第一种情况：没找到删除的节点，遍历到空节点就返回
        if (root == NULL) return root;
        if (root->val == key){
            //第二种情况：左右孩子都为空(叶子节点)，直接删除节点，返回NULL为根节点
            if (root->left == NULL && root->right == NULL){
                delete root; //内存释放
                return NULL;
            }
            //第三种情况：左孩子为空，右孩子不为空，删除节点后，右孩子补位，返回右孩子为根节点
            else if (root->left == NULL && root->right != NULL){
                TreeNode* pre = root->right;
                //内存释放
                delete root;
                return pre;
            }
            //第四种情况：左孩子不为空，右孩子为空，删除节点后，左孩子补位，返回左孩子为根节点
            else if (root->left != NULL && root->right == NULL){
                TreeNode* pre = root->left;
                //内存释放
                delete root;
                return pre;
            }
            //第五种情况：左右孩子都不为空。删除左点。将左孩子接到右孩子节点的最左侧，并返回右孩子为新的节点
            else{
                TreeNode* cur = root->right;
                //寻找右孩子的最左侧节点
                while (cur->left != NULL){
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* new_root = root->right;
                //内存释放
                delete root;
                return new_root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

? ? ? ? 在该代码中给出了较详细的注释，在递归终止条件的判断中，要考虑五种情况，并且在删除节点后要进行内存释放操作。单层递归逻辑上与上一题相同，依然是通过上下层之间返回值来完成赋值操作。

总结

? ? ? ? 今天二叉搜索树的插入和删除节点操作的练习主要重点理解掌握如何通过递归函数返回值完成新加入节点的父子关系赋值操作。