114. 二叉樹展開為鏈表

題目:給你二叉樹的根結點?root?,請你將它展開為一個單鏈表:

  • 展開后的單鏈表應該同樣使用?TreeNode?,其中?right?子指針指向鏈表中下一個結點,而左子指針始終為?null?。
  • 展開后的單鏈表應該與二叉樹?先序遍歷?順序相同。

方法一:先鋪開再更新Tree

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/var flatten = function(root) {const list = [];preorderTraversal(root,list);const size = list.length;for(let i = 1;i < size;i++){const pre = list[i-1],cur = list[i];pre.left = null;pre.right = cur;}
};const preorderTraversal = (root,list) =>{if(root!==null){list.push(root);preorderTraversal(root.left,list);preorderTraversal(root.right,list);}
}
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {//迭代法平鋪數組//迭代前序遍歷需要用到棧const list = [];const stack = [];let node = root;while(node!==null||stack.length){while(node !== null){list.push(node);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}const size = list.length;for (let i = 1; i < size; i++) {const prev = list[i - 1], curr = list[i];prev.left = null;prev.right = curr;}
};

方法二:迭代加棧實現一邊遍歷一邊更新

用棧保存丟失的左右孩子的信息。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {//一邊遍歷,一邊更新Treeif(root===null){return;}const stack = [];stack.push(root);let pre = null;while(stack.length){const cur = stack.pop();if(pre !== null){pre.left = null;pre.right = cur;}const left = cur.left,right = cur.right;if(right !== null){stack.push(right);}if(left!==null){stack.push(left);}pre = cur;}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/96091.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/96091.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/96091.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

【Langchain系列三】GraphGPT——LangChain+NebulaGraph+llm構建智能圖數據庫問答系統

Langchain二次開發專欄 【Langchain系列一】常用大模型的key獲取與連接方式 【Langchain系列二】LangChain+Prompt +LLM智能問答入門 【Langchain系列三】GraphGPT——LangChain+NebulaGraph+llm構建智能圖數據庫問答系統 【Langchain系列四】RAG——基于非結構化數據庫的智能問…

【GNSS定位原理及算法雜記6】??????PPP(精密單點定位)原理,RTK/PPK/PPP區別討論

PPP 技術詳解&#xff1a;原理、流程與 RTK/PPK 對比 在高精度 GNSS 定位技術體系中&#xff0c;除了 RTK 和 PPK 以外&#xff0c;還有一類無需基站即可實現分米到厘米級定位的方法 —— PPP&#xff08;Precise Point Positioning&#xff0c;精密單點定位&#xff09;。它以…

LeetCode 837.新 21 點:動態規劃+滑動窗口

【LetMeFly】837.新 21 點&#xff1a;動態規劃滑動窗口 力扣題目鏈接&#xff1a;https://leetcode.cn/problems/new-21-game/ 愛麗絲參與一個大致基于紙牌游戲 “21點” 規則的游戲&#xff0c;描述如下&#xff1a; 愛麗絲以 0 分開始&#xff0c;并在她的得分少于 k 分時…

Codeforces 盒裝蘋果

題目來源&#xff1a;問題 - 2107B - Codeforces 這道題其實只需要判斷兩個要點&#xff0c;首先判斷一下最大值-1后與最小值的差值是否>k&#xff0c;這里有個小細節&#xff0c;當有多個最大值時&#xff0c;可以先將一個最大值-1后再排序&#xff0c;判斷新數組最大值與最…

數據結構--------堆

目錄 二叉樹 樹的概念與結構 非樹形結構&#xff1a; 注意&#xff1a; 樹的相關術語 樹的表示 孩子兄弟表示法 樹形結構實際運用場景&#xff08;拓展&#xff09; 1. 文件系統管理 2. 數據庫與索引 3. 編程語言與數據結構 信息組織與展示 1. 思維導圖 2. 目錄與…

VSCode Cursor 大模型 插件擴展 Kilo Code 配置

1.1 概述 Kilo Code 是一個 VSCode Cursor 插件擴展&#xff0c;提供了對多種 AI 模型的支持&#xff0c;包括 Claude Code 和 Qwen3。通過正確配置 Kilo Code&#xff0c;可以在開發過程中獲得更好的 AI 輔助編程體驗。 Kilo使用文檔&#xff1a;https://kilocode.ai/docs/zh-…

深入解析:Unity、Unreal Engine與Godot引擎中的Uniform變量管理

在現代游戲開發中&#xff0c;Uniform變量是實現高質量圖形渲染的關鍵元素。不同游戲引擎對Uniform變量的管理方式有所不同&#xff0c;了解這些差異可以幫助開發者在選擇引擎時做出更明智的決策。本文將深入探討Unity、Unreal Engine和Godot引擎中Uniform變量的管理方式&#…

遨游旅游天地,開啟探索未知的夢幻之旅

你是否也懷揣著一顆對世界充滿好奇的心&#xff0c;渴望踏上探索旅游世界的奇妙旅程&#xff1f;旅游&#xff0c;是一場與未知的邂逅&#xff0c;是心靈的一次自由翱翔。想象一下&#xff0c;你置身于神秘莫測的撒哈拉沙漠。當夕陽的余暉灑在連綿起伏的沙丘上&#xff0c;那金…

SConscript 腳本入門教程

第一章&#xff1a;什么是 SCons 和 SConscript&#xff1f;核心概念SCons 是一個現代化的構建工具&#xff0c;用于自動化軟件構建過程&#xff0c;類似于 Make 但功能更強大、語法更簡潔。SConstruct&#xff1a;是 SCons 的主配置文件&#xff0c;通常在項目根目錄&#xff…

【深度學習】PyTorch從0到1——手寫你的第一個卷積神經網絡模型,AI模型開發全過程實戰

引言本次準備建立一個卷積神經網絡模型&#xff0c;用于區分鳥和飛機&#xff0c;并從CIFAR-10數據集中選出所有鳥和飛機作為本次的數據集。以此為例&#xff0c;介紹一個神經網絡模型從數據集準備、數據歸一化處理、模型網絡函數定義、模型訓練、結果驗證、模型文件保存&#…

云計算核心技術之容器技術

一、容器技術 1.1、為什么需要容器 在使用虛擬化一段時間后&#xff0c;發現它存在一些問題&#xff1a;不同的用戶&#xff0c;有時候只是希望運行各自的一些簡單程序&#xff0c;跑一個小進程。為了不相互影響&#xff0c;就要建立虛擬機。如果建虛擬機&#xff0c;顯然浪費就…

微信小程序通過uni.chooseLocation打開地圖選擇位置,相關設置及可能出現的問題

前言 uni.chooseLocation打開地圖選擇位置&#xff0c;看官方文檔介紹的比較簡單&#xff0c;但是需要注意的細節不少&#xff0c;如果沒有注意可能就無法使用該API或者報錯&#xff0c;下面就把詳細的配置方法做一下介紹。 一、勾選位置接口 ①在uniapp項目根目錄找到manif…

從財務整合到患者管理:德國醫療集團 Asklepios完成 SAP S/4HANA 全鏈條升級路徑

目錄 挑戰 解決方案 詳細信息 Asklepios成立于1985年&#xff0c;目前擁有約170家醫療機構&#xff0c;是德國大型私營診所運營商。Asklepios是希臘和羅馬神話中的醫神。 挑戰 Asklepios希望進一步擴大其作為數字醫療保健集團的地位。2020年9月&#xff0c;該公司與SNP合作…

高頻PCB廠家及工藝能力分析

一、技術領先型廠商&#xff08;適合高復雜度、高可靠性設計&#xff09;這類廠商在高頻材料處理、超精密加工和信號完整性控制方面具備深厚積累&#xff0c;尤其適合軍工、衛星通信、醫療設備等嚴苛場景&#xff1a;深南電路&#xff1a;在超高層板和射頻PCB領域是行業標桿&am…

AJAX 與 ASP 的融合:技術深度解析與應用

AJAX 與 ASP 的融合:技術深度解析與應用 引言 隨著互聯網技術的不斷發展,AJAX(Asynchronous JavaScript and XML)和ASP(Active Server Pages)技術逐漸成為構建動態網頁和應用程序的重要工具。本文將深入探討AJAX與ASP的融合,分析其原理、應用場景以及在實際開發中的優…

MuMu模擬器Pro Mac 安卓手機平板模擬器(Mac中文)

原文地址&#xff1a;MuMu模擬器Pro Mac 安卓手機平板模擬器 MuMu模擬器 Pro mac版&#xff0c;是一款MuMuPlayer安卓模擬器&#xff0c;可以暢快運行安卓游戲和應用。 MuMu模擬器Pro搭載安卓12操作系統&#xff0c;極致釋放設備性能&#xff0c;最高支持240幀畫面效果&#…

Oracle維護指南

Part 1 Oracle 基礎與架構#### **1.1 概述** - **Oracle 數據庫版本歷史與特性對比** - **版本演進**&#xff1a; - Oracle 8i&#xff08;1999&#xff09;&#xff1a;支持 Internet 應用&#xff0c;引入 Java 虛擬機&#xff08;JVM&#xff09;。 - Oracle 9i&#…

如何為PDF文件批量添加騎縫章?

騎縫章跨越多頁文件的邊緣加蓋&#xff0c;一旦文件被替換其中某一頁或順序被打亂&#xff0c;印章就無法對齊&#xff0c;能立刻發現異常。這有效保障了文件的完整性和真實性。它是純凈免費&#xff0c;不帶廣告&#xff0c;專治各類PDF蓋章需求。用法極簡&#xff1a;文件直接…

組合時代的 TOGAF?:為模塊化企業重新思考架構

隨著企業努力追求敏捷性和創新性&#xff0c;組合性正逐漸成為一項基礎性的設計原則。組合思維改變了企業交付能力的方式 —— 更傾向于采用模塊化、獨立的組件&#xff0c;這些組件可以快速組裝和重組。本文探討了長期以來作為企業架構框架的TOGAF標準如何演進以支持組合架構。…

電子元器件-電阻終篇:基本原理,電阻分類及特點,參數/手冊詳解,電阻作用及應用場景,電阻選型及實戰案例

目錄 一、基本原理 1.1 介紹 1.2 計算公式?編輯 1.3 單位 1.4 標稱值 二、分類及特點 2.1電阻分類及特點介紹 2.2常用電阻器件詳細介紹 三、參數/數據手冊解讀 3.1 阻值 3.2 封裝&功率 3.3 精度 3.5 額定電壓 3.6 溫度系數(TCR) 3.7 擴展 四、作用與使用場…