前言 今天複習了一些前端演算法題,寫到一兩道比較有意思的題:重建二叉樹、反向輸出鏈表每個節點 題目 重建二叉樹: 輸入某二叉樹的前序遍歷和中序遍歷的結果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列 {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
上述為個人整理內容,水平有限,如有錯誤之處,望各位園友不吝賜教!如果覺得不錯,請點個贊和關註支持一下!謝謝~๑•́₃•̀๑ [鮮花][鮮花][鮮花]