資訊專(zhuān)欄INFORMATION COLUMN
摘要：代碼層序遍歷復(fù)雜度時(shí)間空間對(duì)于二叉樹(shù)思路我們同樣可以借用層序遍歷的思路，只要每次把這一層的最后一個(gè)元素取出來(lái)就行了，具體代碼參見(jiàn)中的
Binary Tree Right Side View
深度優(yōu)先搜索 復(fù)雜度Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example: Given the following binary tree,
1 <--- / 2 3 <--- 5 4 <---You should return [1, 3, 4].
時(shí)間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對(duì)于二叉樹(shù)b=2
思路本題實(shí)際上是求二叉樹(shù)每一層的最后一個(gè)節(jié)點(diǎn)，我們用DFS先遍歷右子樹(shù)并記錄遍歷的深度，如果這個(gè)右子節(jié)點(diǎn)的深度大于當(dāng)前所記錄的最大深度，說(shuō)明它是下一層的最右節(jié)點(diǎn)（因?yàn)槲覀兿缺闅v右邊，所以每一層都是先從最右邊進(jìn)入），將其加入結(jié)果中。
代碼public class Solution {
int maxdepth = 0;
List res;
public List rightSideView(TreeNode root) {
res = new LinkedList();
if(root!=null) helper(root,1);
return res;
}
private void helper(TreeNode root, int depth){
if(depth>maxdepth){
maxdepth = depth;
res.add(root.val);
}
if(root.right!=null) helper(root.right, depth+1);
if(root.left!=null) helper(root.left, depth+1);
}
}
層序遍歷 Level Order Traversal
復(fù)雜度
時(shí)間 O(b^(h+1)-1) 空間 O(b^h) 對(duì)于二叉樹(shù)b=2
思路我們同樣可以借用層序遍歷的思路，只要每次把這一層的最后一個(gè)元素取出來(lái)就行了，具體代碼參見(jiàn)Binary Tree Traversal中的Binary Tree Level Order Traversal
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64469.html
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g對(duì)于二叉樹(shù)思路簡(jiǎn)單的二叉樹(shù)遍歷，遍歷的過(guò)程中記錄之前的路徑，一旦遍歷到葉子節(jié)點(diǎn)便將該路徑加入結(jié)果中。當(dāng)遇到最小公共祖先的時(shí)候便合并路徑。需要注意的是，我們要單獨(dú)處理目標(biāo)節(jié)點(diǎn)自身是最小公共祖先的情況。 Root To Leaf Binary Tree Paths Given a binary tree, return all root-to-leaf pat...
摘要：原題鏈接遞歸法復(fù)雜度時(shí)間空間遞歸棧空間思路這個(gè)難倒大神的題也是非常經(jīng)典的一道測(cè)試對(duì)二叉樹(shù)遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點(diǎn)或葉子節(jié)點(diǎn)時(shí)，不再交換，直接返回該節(jié)點(diǎn)。代碼給出的是后序遍歷的自下而上的交換，先序遍歷的話(huà)就是自上而下的交換。 Invert Binary Tree Invert a binary tree. 4 / 2 7 / ...
LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹(shù)的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...
閱讀 2351·2021-11-24 10:18
閱讀 2812·2021-11-19 09:59
閱讀 1767·2019-08-30 15:53
閱讀 1248·2019-08-30 15:53
閱讀 1120·2019-08-30 14:19
閱讀 2540·2019-08-30 13:14
閱讀 3085·2019-08-30 13:00
閱讀 2081·2019-08-30 11:11
