【经典题】二叉搜索树与双向链表

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

二叉搜索树与双向链表链接

解题思路

思路1 : 中序遍历,将节点放进vector中,再改链接关系,这很容易想出并解决,但这样明显不符合题意。
【经典题】二叉搜索树与双向链表

思路2:
这道题目要求将一个二叉搜索树转换成一个排序的双向链表,不创建新的节点,只调整指针。
二叉搜索树的特点是左子树的值都小于根节点,右子树的值都大于根节点,中序遍历可以得到一个升序的序列。
因此,我们可以利用中序遍历的顺序,将每个节点的左指针指向前一个节点,将每个节点的右指针指向后一个节点,从而形成一个双向链表。
我们需要用一个变量prev来记录前一个节点,初始为nullptr。然后我们递归遍历二叉树,每次访问到一个节点时,就修改它和prev的指针,并更新prev为当前节点。
最后,我们从根节点开始往左走,找到最左边的节点,即双向链表的头节点,返回即可。
【经典题】二叉搜索树与双向链表

举个栗子:
假设我们有这样一个二叉搜索树:

       10
      /  \
    6    14
    / \   / \
   4   8 12 16

我们先初始化prev为空,然后从根节点开始递归遍历二叉树。

首先我们遍历到4这个节点,它没有左子树,所以我们直接修改它的左指针指向prev(此时为空),然后将prev更新为4。

然后我们回到6这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为4),并将4的右指针指向6。然后将prev更新为6。

然后我们遍历到8这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为6),并将6的右指针指向8。然后将prev更新为8。

然后我们回到10这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为8),并将8的右指针指向10。然后将prev更新为10。

然后我们遍历到12这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为10),并将10的右指针指向12。然后将prev更新为12。

然后我们回到14这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为12),并将12的右指针指向14。然后将prev更新为14。

然后我们遍历到16这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为14),并将14的右指针指向16。然后将prev更新为16。

最后我们回到根节点10,并从它开始往左走,找到最左边的节点4,即双向链表的头节点。返回4即可。

此时二叉搜索树已经转换成了如下的双向链表:

NULL <-> 4 <-> 6 <-> 8 <-> 10 <-> 12 <-> 14 <-> 16 <-> NULL
【经典题】二叉搜索树与双向链表

代码—加注释

/*
struct TreeNode {
    int val; // 节点的值
    struct TreeNode *left; // 左子节点的指针
    struct TreeNode *right; // 右子节点的指针
    TreeNode(int x) : // 构造函数,初始化节点的值和子节点指针
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    void InOrderConvert(TreeNode* cur, TreeNode*& prev) {
        if (cur == nullptr) // 如果当前节点为空,直接返回
            return;
        InOrderConvert(cur->left, prev); // 递归遍历左子树
        //这里cur出现的顺序就是中序
        cur->left = prev; // 将当前节点的左指针指向前一个节点
        if (prev) // 如果前一个节点不为空,将其右指针指向当前节点
            prev->right = cur;
        prev = cur; // 更新前一个节点为当前节点

        InOrderConvert(cur->right, prev); // 递归遍历右子树
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr; // 初始化前一个节点为空
        InOrderConvert(pRootOfTree,
                       prev); // 调用辅助函数,中序遍历二叉树,并修改指针

        TreeNode* head = pRootOfTree; // 初始化头节点为根节点
        while (head &&
                head->left) { // 循环找到最左边的节点,即双向链表的头节点
            head = head->left;
        }


        return head; // 返回头节点
    }
};

本节完文章来源地址https://www.toymoban.com/news/detail-427362.html

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

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

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

相关文章

  • 算法与数据结构--二叉搜索树与自平衡二叉搜索树

    注:字典的 \\\"member运算\\\" 指的是检查字典中是否存在某个特定的键的操作,即查询操作。 如果我们使用数组来实现字典/map,虽然使用二分法查询也可以达到logn,但是的话插入和删除太慢了。使用链表实现的话虽然插入和删除是O(1),但是查询的话达到了O(n),也不可取。 因此人

    2024年02月04日
    浏览(37)
  • 【数据结构】二叉搜索树与Map和Set

    目录 ♫二叉搜索树 ♪什么是二叉搜索树 ♪二叉搜索树的特性 ♪模拟实现二叉搜索树 ♫Map ♪什么是Map ♪Map的内部类 ♪Map的常用方法 ♪Map的遍历 ♫Set  ♪什么是Set ♪Set的常用方法 ♪Set的遍历 ♪什么是二叉搜索树 二叉搜索树又称二叉排序树,是一种特殊的二叉树,这颗树

    2024年02月07日
    浏览(40)
  • 【C++】二叉搜索树经典OJ题目

    解题思路 这道题是让我们使用前序遍历的方式来创建字符串,但是有一点需要注意的是,再创建的字符串中,需要将每一个左右子树用括号括起来。这里扩括号的时候有两点需要注意的细节: 当左右子树都为空时,该节点左右子树的括号都可以省略掉。 当左子树不为空,右

    2024年02月05日
    浏览(38)
  • Leetcode面试经典150题刷题记录 —— 二叉搜索树篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试经典

    2024年01月23日
    浏览(63)
  • Java LeetCode篇-二叉搜索树经典解法(实现:二叉搜索树的最近公共祖先、根据前序遍历建树等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 判断合法         1.1 使用遍历方式实现验证二叉搜索树         1.2 使用递归方式实现验证二叉搜索树         2.0 求范围和         2.1 使用非递归实现二叉搜索树的范围和

    2024年02月03日
    浏览(45)
  • 力扣0109——有序链表转换二叉搜索树

    难度: 中等 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-

    2024年02月21日
    浏览(37)
  • OJ练习第137题——有序链表转换二叉搜索树

    力扣链接:109. 有序链表转换二叉搜索树 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 来源:力扣(LeetCode) 链接:https://leetcode.cn/

    2024年02月16日
    浏览(33)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 数据结构:图文详解 树与二叉树(树与二叉树的概念和性质,存储,遍历)

    目录 一.树的概念 二.树中重要的概念 三.二叉树的概念 满二叉树 完全二叉树 四.二叉树的性质 五.二叉树的存储 六.二叉树的遍历 前序遍历 中序遍历  后序遍历  树是一种 非线性数据结构 ,它由节点和边组成。树的每个节点可以有零个或多个子节点,其中一个节点被指定为

    2024年02月04日
    浏览(49)
  • 二叉树与堆

    目录 一、二叉树 1、二叉树的概念及结构 1.1、树的概念 1.2、二叉树的概念 1.3、二叉树的存储结构 1.3.1、顺序结构存储 1.3.2、链式结构存储 2、二叉树的实现(链式结构) 2.1、二叉树的遍历 2.1.1、前序、中序以及后序遍历 2.1.2、层序遍历 2.2、二叉树链式结构的代码实现 二、

    2024年02月10日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包