1. 110平衡二叉樹
本題平衡的定義是一個二叉樹每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 一也。
- 某節(jié)點深度:是到根節(jié)點的距離,根節(jié)點起始就是1(leetcode定義)
- 某節(jié)點高度:是從該到其子葉節(jié)點的距離.
(是到它自己的子葉節(jié)點,所以下面哪個圖,val=0節(jié)點的高度是1)
image.png
對應(yīng)的:
-
求高度就用后序遍歷,求深度就用前序遍歷.
至于為什么求二叉樹最大深度的時候用的是后序遍歷,因為:
代碼的邏輯其實是求的根節(jié)點的高度攻走，而根節(jié)點的高度就是這棵樹的最大深度蚯斯，所以才可以使用后序遍歷。
先定義左右兩邊高度,并判斷是-1直接返回-1.
那-1是怎么賦值的呢?就是我們的判斷條件.高度差.所以要判斷高度差.
(要先判斷單邊高度,因為-1-(-1) = 0也小于1,但是根本不是我們要的)
剩下的就能返回上一層了,也就是中
2. 257.二叉樹所有路徑
第一遍刷太難了.完全不知道在分叉路口應(yīng)該怎么做,腦袋里用現(xiàn)成的方法就是前序.
回溯和遞歸是相輔相成的,回溯就是比如你已經(jīng)找到了1->2->5,把5彈出去叫回溯,把2彈出去也叫回溯.
目前用不到,js的遞歸用的是一直加
- 要準備兩個variable,一個res=[]用來存結(jié)果,一個curPath = ' '用來存路徑
- 重點看下這道題的左右怎么處理的
404.左子葉之和
難點:我們沒法判斷葉子節(jié)點是不是父節(jié)點的左孩子,
方法:靠父節(jié)點.
image.png
比如這個圖里我們想拿6,要在9的地方就判斷:
9的左孩子不為空
&&
該左孩子沒有左右孩子,也就是是葉子節(jié)點
該題用后序比較方便,左右的和直接+就行了
看代碼好像出現(xiàn)了三個value,我第一反應(yīng)是leftValue不會和midValue重疊嗎,但是實際上leftValue那部分是遞歸的必要,不然他怎么往下走呢.而且邏輯是在當前節(jié)點計算子節(jié)點的值如果是葉子節(jié)點的話
