1. 654.最大二叉樹
重點(diǎn)是先把題讀明白,先找最大根節(jié)點(diǎn),左邊的就是左子樹,右邊的就是右子樹,對(duì)子樹也進(jìn)行相同的操作.意思是不是左子樹的子節(jié)點(diǎn)就都在左邊,左子樹拿出來最大的比如是第二個(gè)元素,那第二個(gè)元素右邊的元素就得是第二個(gè)元素作為根節(jié)點(diǎn)的右子樹.
凡是構(gòu)建二叉樹的題都要用前序遍歷:
因?yàn)橐确鸥?jié)點(diǎn),也就是中
以及在給的funtion再寫function遞歸是因?yàn)?需要傳進(jìn)去別的參數(shù),如果只需要每次遞歸傳root當(dāng)然可以不用套function
- 本題在找最大點(diǎn)的時(shí)候每次遞歸都是把整個(gè)數(shù)組傳遞,只改變left和right的index,從而不斷縮小范圍.所以不能用math的方法,因?yàn)槟菢臃祷氐氖钦麄€(gè)數(shù)組的結(jié)果,除非用slice分兩個(gè)數(shù)組.但是這樣會(huì)特別慢,可能會(huì)超時(shí),因?yàn)槊總€(gè)數(shù)組都會(huì)創(chuàng)建兩次.
2. 617.合并二叉樹
大體思路知道了,但是不看題解真的不知道怎么操作,比如寫著寫著情況就越來越多了,我一開始寫了這些
node1.left&&node2.left&&mergeAll(node1.left,node2.left);
node1.right&&node2.right&&mergeAll(node1.left,node2.left);
這樣寫寫不完了.
題解用的方法是在在一棵樹上修改.按規(guī)則加或不加另一個(gè)樹的值.
對(duì)于子節(jié)點(diǎn)不用那么復(fù)雜,左邊就都用傳進(jìn)去left,根據(jù)返回條件,就算都是null也沒事
3. 700.二叉搜索樹(BST)中的搜索
這道題思路自己想出來了,但是代碼實(shí)現(xiàn)有些問題.這是我的版本
var searchBST = function(root, val) {
const searchNode = function(node){
if(node.val === val) return node;
if(node.val >val){
node.left && searchNode(node.left);
}
if(node.val <val){
node.right && searchNode(node.right);
}
}
return searchNode(root)
};
這個(gè)版本沒法處理node是null的情況,而且也沒有返回node,要用return 一層一層向上返回
題解的版本把===val 和!node放一起處理了,因?yàn)槎际欠祷豱ode
4.98.驗(yàn)證二叉搜索樹
我看到的思考:
要存最大值,每次進(jìn)的時(shí)候比較
進(jìn)左就要比當(dāng)前節(jié)點(diǎn)小.
不能只有一個(gè)子樹
我的寫法:
var isValidBST = function(root) {
const BST = function(node){
if(!node.left&&node.right||node.left&&!node.right) return false;
if(node.left&&node.left.val>=node.val ||node.right&&node.right.val<=node.val) return false;
if(node.left){
return BST(node.left);
}
if(node.right){
return BST(node.right)
}
return true
}
return BST(root);
};
直接掉進(jìn)陷阱里了
image.png
- 遇到搜索樹,記得用中序遍歷,
中序遍歷的特點(diǎn):輸出的節(jié)點(diǎn)的數(shù)值是有序數(shù)列,
所以驗(yàn)證是不是二叉搜索樹就轉(zhuǎn)化為判斷序列是不是遞增的,遞歸的時(shí)候把值push進(jìn)輔助數(shù)組,判斷輔助數(shù)組就好了
