資訊專欄INFORMATION COLUMN
摘要：樹的前序，中序遍歷的結(jié)構(gòu)如下圖可以看出，通過(guò)前序遍歷可以確定根節(jié)點(diǎn)，再通過(guò)中序遍歷和根節(jié)點(diǎn)的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。
從前序與中序遍歷序列構(gòu)造二叉樹
今天帶來(lái)的是Leetcode上的一個(gè)經(jīng)典題：從前序與中序遍歷序列構(gòu)造二叉樹
原題干：
/**
Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
*/
/**@param {number[]} preorder
@param {number[]} inorder
@return {TreeNode}
*/
input:前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
output： 樹的根節(jié)點(diǎn)
條件：
樹的結(jié)構(gòu)為：{ val, left, right }
下面是我解決這個(gè)題的時(shí)候的思路
解題思路這個(gè)題目考察的是對(duì)樹結(jié)構(gòu)和樹遍歷的熟悉程度。樹的前序，中序遍歷的結(jié)構(gòu)如下圖：
可以看出，通過(guò)前序遍歷可以確定根節(jié)點(diǎn)，再通過(guò)中序遍歷和根節(jié)點(diǎn)的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。
因此可以確定有一種遞歸解法。確定根和左右子樹，遞歸用左右子樹的前序和中序順序去獲取左右子樹。
代碼var buildTree = function(preorder, inorder) {
if (preorder.length === 0) {
return null
}
let leftTreeLen = 0
let rightTreeLen = 0
let tag = 1
for (let i = inorder.length - 1; i >= 0; i--) {
if (inorder[i] !== preorder[0]) {
if (tag) {
rightTreeLen++
} else {
leftTreeLen++
}
} else if (inorder[i] === preorder[0]) {
tag = false
}
}
let root = new TreeNode(preorder[0]) // 根
root.left = buildTree(preorder.slice(1, 1 + leftTreeLen), inorder.slice(0, leftTreeLen))
root.right = buildTree(preorder.slice(1 + leftTreeLen), inorder.slice(-rightTreeLen))
return root
};
晚上再更新一次，目測(cè)是有非遞歸的解法的。
本期算法小分享就到這里咯（leetcode正在做完探索里的中級(jí)。）如果有什么意見或者想法歡迎在評(píng)論區(qū)和我交流
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/107905.html
摘要：二叉搜索樹的特性二叉搜索樹由于其獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，使得其無(wú)論在增刪，還是查找，時(shí)間復(fù)雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡(jiǎn)單，根據(jù)左子節(jié)點(diǎn)比該節(jié)點(diǎn)小，右子節(jié)點(diǎn)比該節(jié)點(diǎn)大的原則進(jìn)行循環(huán)判斷即可。 什么是二叉樹 二叉樹就是樹的每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn) 什么是二叉搜索樹 二叉搜索樹在二叉樹的基礎(chǔ)上，多了一個(gè)條件，就是二叉樹在插入值時(shí)，若插入值比當(dāng)前節(jié)點(diǎn)小，就插入到左節(jié)點(diǎn)，否則插...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由于二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為每個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域。最終能得到二叉樹的完整結(jié)構(gòu)。這篇文章主要介紹樹結(jié)構(gòu)中的一種特殊存在——二叉樹。主要內(nèi)容有： 二叉樹的概念 二叉樹的基本結(jié)構(gòu) 二叉樹的操作 概念 二叉樹： 每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，兩個(gè)子結(jié)點(diǎn)是有次序的，且子結(jié)點(diǎn)次序不能顛倒。兩個(gè)子結(jié)點(diǎn)一般稱之為左結(jié)點(diǎn)及右結(jié)點(diǎn)。 層次： 在樹中，節(jié)點(diǎn)的層次從...
摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實(shí)現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實(shí)現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點(diǎn)擊鏈接感受下筆者用d3.js畫的tree https://codepen...
閱讀 2704·2021-09-22 15:58
閱讀 2241·2019-08-29 16:06
閱讀 915·2019-08-29 14:14
閱讀 2818·2019-08-29 13:48
閱讀 2465·2019-08-28 18:01
閱讀 1513·2019-08-28 17:52
閱讀 3334·2019-08-26 14:05
閱讀 1628·2019-08-26 13:50
