代码随想录二刷day22 |二叉树之 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

这篇具有很好参考价值的文章主要介绍了代码随想录二刷day22 |二叉树之 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

题目链接
解题思路:讨论 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p,其余的情况的最近公共祖先就是根节点。
使用递归三部曲

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

参数就是当前节点,以及两个结点 p、q。

返回值是要返回最近公共祖先,所以是TreeNode * 。

代码如下:

TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
  1. 确定终止条件

遇到空返回就可以了,代码如下:

if (cur == NULL) return cur;

其实都不需要这个终止条件,因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的,所以并不存在遇到空的情况。

  1. 确定单层递归的逻辑

在遍历二叉搜索树的时候就是寻找区间[p->val, q->val](注意这里是左闭右闭)

那么如果 cur->val 大于 p->val,同时 cur->val 大于q->val,那么就应该向左遍历(说明目标区间在左子树上)。

需要注意的是此时不知道p和q谁大,所以两个都要判断

代码如下:

if (cur->val > p->val && cur->val > q->val) {
    TreeNode* left = traversal(cur->left, p, q);
    if (left != NULL) {
        return left;
    }
}

代码如下:

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);
            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;  // 如果是一左一右,则cur就是最近公共祖先
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};


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

题目链接
解题思路:
递归三部曲:

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

参数就是根节点指针,以及要插入元素,这里递归函数要不要有返回值呢?

可以有,也可以没有,但递归函数如果没有返回值的话,实现是比较麻烦的,下面也会给出其具体实现代码。

有返回值的话,可以利用返回值完成新加入的节点与其父节点的赋值操作。

递归函数的返回类型为节点类型TreeNode * 。

代码如下:

TreeNode* insertIntoBST(TreeNode* root, int val)
  1. 确定终止条件

终止条件就是找到遍历的节点为null的时候,就是要插入节点的位置了,并把插入的节点返回。

代码如下:

if (root == NULL) {
    TreeNode* node = new TreeNode(val);
    return node;
}

这里把添加的节点返回给上一层,就完成了父子节点的赋值操作了,详细再往下看。

  1. 确定单层递归的逻辑

搜索树是有方向了,可以根据插入元素的数值,决定递归方向。

代码如下:

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将其接住。

整体代码如下:

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

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

题目链接
解题思路:
递归三部曲:

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

说到递归函数的返回值,在上一题中通过递归返回值来加入新节点, 这里也可以通过递归返回值删除节点。

代码如下:

TreeNode* deleteNode(TreeNode* root, int key)
  1. 确定终止条件

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

if (root == nullptr) return root;
  1. 确定单层递归的逻辑

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况:

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

代码如下:

if (root->val == key) {
    // 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
    // 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点
    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; // 把要删除的节点(root)左子树放在cur的左孩子的位置
        TreeNode* tmp = root;   // 把root节点保存一下,下面来删除
        root = root->right;     // 返回旧root的右孩子作为新root
        delete tmp;             // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)
        return root;
    }
}

这里相当于把新的节点返回给上一层,上一层就要用 root->left 或者 root->right接住,代码如下:

if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;

代码如下:文章来源地址https://www.toymoban.com/news/detail-482917.html

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

到了这里,关于代码随想录二刷day22 |二叉树之 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【代码随想录day21】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 这题的难点在于: 如何建

    2024年02月15日
    浏览(44)
  • 代码随想录二刷day01

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 使用左闭右闭区间的二分查找时, 最后low一定是被查找元素的插入位置,若查找的数带小数,low-1, 便是最终结果 1、左闭右闭 2、左闭右开

    2024年02月12日
    浏览(56)
  • 代码随想录二刷day06

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 stream流写法

    2024年02月10日
    浏览(42)
  • 代码随想录二刷day48

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    2024年02月07日
    浏览(91)
  • 代码随想录二刷day35

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    2024年02月07日
    浏览(65)
  • 代码随想录二刷day17

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 二叉树中深度指的是根节点到当前节点的节点个数, 二叉树中的高度指的是当前节点到叶子节点的节点个数 可以通前序遍历求深度 通过后序遍历求高度 递归 递归 迭代 递归 迭代 递归 递归

    2024年02月09日
    浏览(46)
  • 代码随想录二刷day16

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 递归 迭代 迭代 递归 迭代 递归 迭代 递归

    2024年02月09日
    浏览(46)
  • 二刷代码随想录——动态规划day40

    一个本硕双非的小菜鸡,备战24年秋招,计划二刷完卡子哥的刷题计划,加油! 二刷决定精刷了,于是参加了卡子哥的刷题班,训练营为期60天,我一定能坚持下去,迎来两个月后的脱变的,加油! 推荐一手卡子哥的刷题网站,感谢卡子哥。代码随想录 终于来到了守关boss。

    2024年03月11日
    浏览(57)
  • 【代码随想录day19】从前序与中序遍历序列构造二叉树

    使用递归建树,流程如下: 取出后序节点创建新树的节点 找到新树的节点在中序中的索引 分割中序序列 分割后序序列 继续递归建立整颗新树

    2024年02月15日
    浏览(34)
  • 代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树

    本文思路和详细讲解来自于:代码随想录 (programmercarl.com) 题目链接:102. 二叉树的层序遍历 - 力扣(LeetCode) 本题使用队列辅助完成,讲解主要函数CheckOrder:首先判断root是否为空,是就直接返回,然后创建队列,向里加入root元素,计算队列的长度,也就是每一层的元素个数,while循环,si

    2024年02月06日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包