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

FreeZinG 发布于2019-08-22 18:32 / 2365人阅读

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

题目描述

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

分析

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

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

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

GPU云服务器云服务器二叉链表双向链表二叉树转链表java java双向链表

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

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

学习JavaScript数据结构与算法（四）：二叉搜索树

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

ingood 2019-08-19 17:26 评论0 收藏0
一文掌握关于Java数据结构所有知识点（欢迎一起完善）

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

keithxiaoy 2019-08-15 15:54 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

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

Genng 2021-11-24 09:39 评论0 收藏0