国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【刷算法】二叉搜索樹與雙向鏈表

FreeZinG / 2379人閱讀

摘要：題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

題目描述

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

分析

如果是這樣一棵二叉搜索樹：




那么它對應的雙向鏈表順序為：

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/95974.html

相關文章

  • 學習JavaScript數據結構與算法（四）：二叉搜索樹

    摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學習的內容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節點成為鍵，這是術語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法四二叉搜索樹 本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據...

    ingood 評論0 收藏0

  • 一文掌握關于Java數據結構所有知識點（歡迎一起完善）

    摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。 在我們學習Java的時候，很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...

    keithxiaoy 評論0 收藏0

  • ＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

    摘要：有效二叉搜索樹定義如下節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

    Genng 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<