资讯专栏INFORMATION COLUMN

【刷算法】二叉搜索树与双向链表

FreeZinG / 2291人阅读

摘要:题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

分析

如果是这样一棵二叉搜索树:




那么它对应的双向链表顺序为:

 
    1 3 4 5 7 10 11 15

仔细观察发现这个序列和树的中序遍历是一样的,所以算法就好写了,先中序遍历得到一个序列,然后再按照双向链表的指针规则链接起来即可。

代码实现
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(r)
{
    if(r === null)
        return r;
    var q = [], s = [];
    var cur = r;
    
    while(cur !== null || s.length !== 0) {
        if(cur !== null){
            s.push(cur);
            cur = cur.left;
        }else{
            cur = s.pop();
            q.push(cur);
            cur = cur.right;
        }
    }
    
    r = q.shift();
    r.left = null;
    r.right = null;
    var tail = r;
    cur = null;
    while(q.length !== 0){
        cur = q.shift();
        tail.right = cur;
        cur.left = tail;
        tail = cur;
    }
    
    return r;
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/95974.html

相关文章

  • ❤️两万字《算法 + 数据结构》如何开始❤️

    文章目录 1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性?1、适用人群?2、有何作用?3、算法简介?4、数据结构 3️⃣如何开始持续的刷题?1、立军令状?‍❤️‍?2、培养兴趣?3、狂切水题??4、养成习惯?5、一周出师 4️⃣简单数据结构的掌握?1、数组?2、字符串?3、链表?4、哈希表?‍?‍?5、队列?‍?‍?‍?6、栈?7、二叉树?8、多叉树?9、森林?10、树状数组?11、...

    BoYang 评论0 收藏0
  • 学习JavaScript数据结构与算法(四):二叉搜索

    摘要:像刚才的这幅图,就是二叉搜索树。而我们本文要学习的内容,就是如何写一个二叉搜索树。但在二叉搜索树中,我们把节点成为键,这是术语。前端路漫漫,且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树 本系列的第一篇文章: 学习JavaScript数据结构与算法(一),栈与队列第二篇文章:学习JavaScript数据结构与算法(二):链表第三篇文章:学习JavaScript数据...

    ingood 评论0 收藏0
  • 一文掌握关于Java数据结构所有知识点(欢迎一起完善)

    摘要:是栈,它继承于。满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。没有键值相等的节点。这是数据库选用树的最主要原因。 在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系统的Java学习以及面试的相关知识。本来是想通过Gitbook的...

    keithxiaoy 评论0 收藏0
  • 二叉树与链表之间的转换

    摘要:对于这种链表转换的题目,都是要通过遍历来解决问题。二二叉树与单链表之间的转换力扣链接题目题目。解法二后序遍历我们通过后续遍历一步步还原,将右子树取出,将左子树转换成右子树,在将原来的右子树接入。 目录 一、二叉树与双链表之间的转换 (1、解法一 (2、解法二 二、二叉树与单链表之间的转换 ...

    wwq0327 评论0 收藏0
  • <LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Pytho

    摘要:有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值,根节点的值均小于右子树的值,因此中序遍历以后得到的序列一定是升序序列。 ...

    Genng 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<