【JavaScript】前端演算法題(重建二叉樹、反向輸出鏈表每個節點)

来源:https://www.cnblogs.com/nothavebug/p/18331362
-Advertisement-
Play Games

前言 今天複習了一些前端演算法題,寫到一兩道比較有意思的題:重建二叉樹、反向輸出鏈表每個節點 題目 重建二叉樹: 輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 { ...


前言

今天複習了一些前端演算法題,寫到一兩道比較有意思的題:重建二叉樹、反向輸出鏈表每個節點

題目

重建二叉樹: 輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6},則重建二叉樹並返回。

思路

前序遍歷(根左右)和中序遍歷(左根右)

思路就是使用遞歸把他分化為每個小的二叉樹,然後都根據前序遍歷(根左右)和中序遍歷(左根右)的特性,前序的首元素就是根,然後再找到中序的根,根的左邊就是左右邊就是右,再進行遞歸,直到前序為null的時候就代表沒有根節點了,那這個元素就是尾節點

一.

①[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]-> val=>1 ->L([2,4,7],[4,7,2]) & R([3,5,6,8],[5,3,8,6]) 根節點 1 ,有左右節點

二.

①L([2,4,7],[4,7,2])-> val=>2 ->L([4,7],[4,7]) && R(null , null) 根節點2(屬1的左節點) ,有左節點,無右節點

②R([3,5,6,8],[5,3,8,6])-> val=>3 ->L([5],[5]) && R([6,8],[6,8]) 根節點3(屬1的右節點) ,有左右節點

三.

①L([4,7],[4,7]) ->val=>4 -> L(null , null) && R([7],[7]) 根節點4(屬2的左節點) ,有右節點,無左節點

②R([6,8],[8,6]) -> val=>6 -> L([8] , [8]) && R(null , null) 根節點6(屬3的右節點),有左節點,無右節點

③L([5],[5]) -> val=>5->(null,null)->終止 尾節點5(屬3的左節點)

四.

①R([7],[7]) -> val=>7 ->終止 尾節點7(屬4的右節點)

②L([8],[8]) -> val=>8 ->終止 尾節點8(屬6的左節點)

代碼實現

function rebuildBinaryTree(front, centre) {
    //判斷是否為空節點
    if (!front || front.length == 0) {
        return null;
    }
    // 根節點
    var TreeNode = {
        val: front[0]
    };
    for (var i = 0; i < front.length; i++) {
        //找到中序遍歷根節點位置
        if (centre[i] === front[0]) {
            //中序遍歷(左根右)
            //根節點左邊的節點為該節點的左邊
            TreeNode.left = rebuildBinaryTree(front.slice(1, i + 1), centre.slice(0, i));
            //根節點右邊的節點為該節點的右邊
            TreeNode.right = rebuildBinaryTree(front.slice(i + 1), centre.slice(i + 1));
        }
    }
    return TreeNode;
}
let tree = rebuildBinaryTree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6])
console.log(tree)

題目

從尾到頭列印鏈表: 輸入一個鏈表,從尾到頭列印鏈表每個節點的值。

思路

由於鏈表是單向的,我們不能直接從頭節點開始反向遍歷。

所以可以使用數組來模擬棧。迭代遍歷鏈表,將鏈表每個節點壓入棧中,然後再依次從棧中彈出並列印。

代碼實現

// 定義一個節點類,結構data表示節點數據、next表示下個節點的指針
class Node {
    constructor(data) {
        this.data = data
        this.next = null
    }
}

function printNode(node) {
    // 定義一個數組表示模擬棧
    let stack = new Array()
    // 初始化當前節點為傳入的節點
    let NodeNextElm = node
    //判斷下個節點指針是否為空
    while (NodeNextElm !== null) {
        //壓棧
        stack.push(NodeNextElm.data)
        //存儲下個節點的指針
        NodeNextElm = NodeNextElm.next
    }
    while (stock.length > 0) {
        //當棧不為空時,迴圈彈出棧頂元素並列印
        console.log(stack.pop())
    }
}
//初始化鏈表
//新建鏈表節點
const node1 = new Node(1)
const node2 = new Node(2)
const node3 = new Node(3)
//手動存儲下個節點的指針
node1.next = node2
node2.next = node3
//調用
printNode(node1)

過程解析

一. 進入,此時的NodeNextElm:{
    "data": 1,
    "next": {
        "data": 2,
        "next": {
            "data": 3,
            "next": null
        }
    }
}

此時進入while迴圈:

①第一次迴圈:

棧stack:[1]

NodeNextElm:{
	"data": 2,
	"next": {
		"data": 3,
		"next": null
	}
}

②第二次迴圈:

棧stack:[1,2]

NodeNextElm:{
	"data": 3,
	"next": null
}

③第三次迴圈:

棧stack:[1,2,3]

NodeNextElm:null

迴圈結束

pop()彈出棧並列印:3,2,1

上述為個人整理內容,水平有限,如有錯誤之處,望各位園友不吝賜教!如果覺得不錯,請點個贊和關註支持一下!謝謝~๑•́₃•̀๑ [鮮花][鮮花][鮮花]


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 引言 在DataOps(數據運營)的推動下,越來越多的企業開始關註數據研發和運營的一體化建設。DataOps通過自動化和流程優化,幫助企業實現數據的高效流轉和管理。 當前,Apache DolphinScheduler作為一款開源的分散式調度系統,憑藉其靈活的插件機制和強大的調度能力,已經成為許多企 ...
  • 近日,第十三屆PostgreSQL技術大會在杭州舉行。本次大會以“聚焦雲端創新,匯聚智慧共用”為主題,行業大咖、學術精英、技術專家和技術愛好者齊聚一堂,共同探討資料庫領域的發展趨勢、技術創新和實踐經驗。中國電信天翼雲受邀參會並斬獲資料庫最佳產品獎。 ...
  • 前言 上一篇文章寫到如何上架IOS應用到Appstore,其中漏掉了些許期間遇到的小坑,現在補上 審核不通過原因 5.1.1 Guideline 5.1.1 - Legal - Privacy - Data Collection and Storage 5.1.1(ii) Permission Ap ...
  • 在我們容器虛擬化產品開發過程中,時長會遇到某些應用無法啟動或運行時異常崩潰的問題;讓應用行為信息豐富,則能還原應用異常發生過程,對我們快速分析問題至關重要。 ...
  • 原文:Jetpack Compose學習(12)——Material Theme的主題色切換-Stars-One的雜貨小窩 閑著無事研究了下Jetpack Compose M3 主題切換效果 本系列以往文章請查看此分類鏈接Jetpack compose學習 如何生成主題 首先,我們需要知道的是,M3 ...
  • RunLoop用於管理事件的迴圈處理機制。運行迴圈在應用程式的主線程中自動啟動,負責監聽和分發各種事件,包括用戶交互(如觸摸事件)、定時器事件、選擇器調用和其他非同步回調。 運行迴圈的作用 運行迴圈的主要作用包括: 處理輸入事件:運行迴圈監聽用戶的輸入,如觸摸、點擊和滑動事件,並將它們分發到適當的處理 ...
  • 在實際開發中,經常需要對tableView或者collectionView執行更新數據源的操作,reloadData是一個常見的方法。這是 UITableView 和 UICollectionView 提供的一個方法,用於重新載入視圖的所有可見行(或項)。 當調用 reloadData 方法時,UI ...
  • AndroidStudio卸載 如果已經安裝:首先先卸載AndroidStudio,最好是使用軟體管理軟體進行卸載(遮這樣卸載的比較乾凈)。 找到你的C:\Users\Administrator.gradle,並且刪除掉【如果出現文件正在占用,你需要重啟電腦,否則刪不掉】 java安裝 我們安卓開 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...