【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

剑指 Offer 36. 二叉搜索树与双向链表

标签

后序遍历、二叉搜索树

步骤

  • 二叉搜索树中的任一节点的直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点。因此,可以通过这个关系来操作原来的二叉树。
  • 为了不影响深度较大的节点的判断,使用后序遍历。

Step1. 后序遍历,寻找 root 的最左侧和最右侧节点,分别设为 head, tail。其中,head 是整棵树最左侧的节点,相当于中序遍历中最先输出的节点。

void postOrder(Node* root) {
    if (root == nullptr) {
        return;
    }
    postOrder(root->left);
    if (!findHead && root->left == nullptr) { // 设置头结点
        head = root;
        findHead = true;
    }
    postOrder(root->right);
    // 找左子树的最右侧节点: 直接前驱
    Node *rightest = findRightest(root->left);
    if (rightest != nullptr) {
        root->left = rightest;
        rightest->right = root;
    }
    // 找右子树的最左侧节点:直接后继
    Node *leftest = findLeftest(root->right);
    if (leftest == nullptr) {
        tail = root;
    } else {
        root->right = leftest;
        leftest->left = root;
    }
}

Step2. 补充寻找指定节点左子树最右侧、右子树最右侧的节点的代码。

/* 	
	Node *leftest  = findLeftest(root->right),
		 *rightest = findRightest(root->left);
 */
Node* findRightest(Node* root) { // 找以root为根的二叉树中,最右侧的节点
    if (root == nullptr) {
        return nullptr;
    }
    while (root->right != nullptr) {
        root = root->right;
    }
    return root;
}
Node* findLeftest(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

Step3. 构建 headtail 之间的联系。文章来源地址https://www.toymoban.com/news/detail-646707.html

head->left = tail;
tail->right = head;

实现代码(C++)

class Solution {
public:
    Node *head, *tail;
    bool findHead = false;
    Node* findRightest(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        while (root->right != nullptr) {
            root = root->right;
        }
        return root;
    }
    Node* findLeftest(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        while (root->left != nullptr) {
            root = root->left;
        }
        return root;
    }
    void postOrder(Node* root) {
        if (root == nullptr) {
            return;
        }
        postOrder(root->left);
        if (!findHead && root->left == nullptr) { // 设置头结点
            head = root;
            findHead = true;
        }
        postOrder(root->right);
        // 找左子树的最右侧节点: 直接前驱
        Node *rightest = findRightest(root->left);
        if (rightest != nullptr) {
            root->left = rightest;
            rightest->right = root;
        }
        // 找右子树的最左侧节点:直接后继
        Node *leftest = findLeftest(root->right);
        if (leftest == nullptr) {
            tail = root;
        } else {
            root->right = leftest;
            leftest->left = root;
        }
    }
    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        postOrder(root);
        head->left = tail;
        tail->right = head;
        return head;
    }
};

到了这里,关于【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【LeetCode-中等】剑指 Offer 31. 栈的压入、弹出序列(详解)

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例

    2024年02月13日
    浏览(40)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(47)
  • 【LeetCode-中等】剑指 Offer 67. 把字符串转换成整数(详解)

    写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续

    2024年02月15日
    浏览(51)
  • 【经典题】二叉搜索树与双向链表

    二叉搜索树与双向链表链接 思路1 : 中序遍历,将节点放进vector中,再改链接关系,这很容易想出并解决,但这样明显不符合题意。 思路2: 这道题目要求将一个二叉搜索树转换成一个排序的双向链表,不创建新的节点,只调整指针。 二叉搜索树的特点是左子树的值都小于

    2024年02月01日
    浏览(46)
  • 每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等&广度优先遍历&剪枝)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+

    2024年02月13日
    浏览(43)
  • 剑指offer33.二叉搜索树的后序遍历序列

     我一开始的想法是:后序遍历是左右根,那么第一个数小于第二个数,第二个数大于第三个数,然后从第三个数开始又循环,显然错了,因为我这种是理想情况,是一个满二叉树。正确的解法是: 后序遍历是[[左子树],[右子树],[根节点]],左子树中的所有值都小于根节点,

    2024年02月16日
    浏览(42)
  • Leetcode-每日一题【剑指 Offer 27. 二叉树的镜像】

    请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入:      4    /     2     7  /   / 1   3 6   9 镜像输出:      4    /     7     2  /   / 9   6 3   1 示例 1: 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 限制: 0 = 节点个数 = 1000 1.题目要求我们设

    2024年02月13日
    浏览(41)
  • (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    难度:简单 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入: 镜像输出: 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制 : 0 = 节点个数 = 1000 注意 :本题与 226. 翻转二叉树 相同。 💡思路:递归 我们从根节点开始,递归地对树进行遍历: 如果

    2024年02月13日
    浏览(33)
  • 剑指 Offer 33. 二叉搜索树的后序遍历序列(java解题)

    目录 1. 题目 2. 解题思路 3. 数据类型功能函数总结 4. java代码 5. 踩坑小记 递归调用,显示 StackOverflowError 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二

    2023年04月22日
    浏览(40)
  • 【leetcode刷题之路】剑指Offer(3)——搜索与回溯算法

    7 搜索与回溯算法 7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树 https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/   这里借助队列来实现广度优先遍历,由于需要访问每一层的节点,而且这一层访问才可以访问下一层,所以可以考虑队列的先进先出,先把每一层的节

    2024年02月13日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包