資訊專欄INFORMATION COLUMN
摘要：題目描述輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。思路二叉樹的大多數(shù)問題可以使用遞歸來解決，本題亦如此。
題目描述
輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。
思路二叉樹的大多數(shù)問題可以使用遞歸來解決，本題亦如此。
首先應(yīng)該有一個(gè)數(shù)組來存儲(chǔ)當(dāng)前路徑上的節(jié)點(diǎn)值，遇到一個(gè)節(jié)點(diǎn)，計(jì)算出和目標(biāo)值還差多少，如果還差0且當(dāng)前節(jié)點(diǎn)已經(jīng)是葉子節(jié)點(diǎn)，那么該路徑就是符合題意的路徑，否則，繼續(xù)向該節(jié)點(diǎn)的左右節(jié)點(diǎn)繼續(xù)遞歸處理下去。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function FindPath(r, expectNumber)
{
var listAll = [];
var list = [];
function find(r, target) {
if(r === null)
return;
list.push(r.val);
target -= r.val;
if(target === 0 && r.left === null && r.right === null)
listAll.push(Array.from(list));
find(r.left, target);
find(r.right, target);
list.pop();
}
find(r, expectNumber)
return listAll;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/95772.html
摘要：假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個(gè)序列的長(zhǎng)度是相等的思路借助一個(gè)輔助棧來存儲(chǔ)數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成，如果出棧順序正確，那么輔助棧應(yīng)該為空。若存在，左右子樹，遞歸檢測(cè)左右子樹是否復(fù)合規(guī)范。 1.包含min函數(shù)的棧 定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。 思路 1.定義兩個(gè)棧，一個(gè)棧用于存儲(chǔ)數(shù)據(jù)，另一個(gè)棧用于存儲(chǔ)每次數(shù)...
摘要：題目描述輸入一棵二叉樹，求該樹的深度。遞歸解法非遞歸解法原來標(biāo)識(shí)當(dāng)前層是否遍歷完畢當(dāng)前彈出元素為時(shí)，說明一層以及遍歷完畢了，所以最后一層的彈出時(shí)不能再往隊(duì)列里面加了 題目描述 輸入一棵二叉樹，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹的深度。 遞歸解法 function TreeNode(x) { this.val = x;...
摘要：題目描述輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。那么對(duì)于二叉搜索樹的后序遍歷的序列來說，最后一個(gè)元素即是它的根節(jié)點(diǎn)，序列的前某部分元素全部小于最后一個(gè)元素，序列的后某部分元素全大于最后一個(gè)元素。 題目描述 輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。 分析 所謂二叉搜索...
閱讀 2936·2021-10-19 10:09
閱讀 3157·2021-10-09 09:41
閱讀 3412·2021-09-26 09:47
閱讀 2729·2019-08-30 15:56
閱讀 618·2019-08-29 17:04
閱讀 1011·2019-08-26 11:58
閱讀 2527·2019-08-26 11:51
閱讀 3387·2019-08-26 11:29
