資訊專欄INFORMATION COLUMN
摘要：代碼層序遍歷復(fù)雜度時間空間對于二叉樹思路我們同樣可以借用層序遍歷的思路，只要每次把這一層的最后一個元素取出來就行了，具體代碼參見中的
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].
時間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對于二叉樹b=2
思路本題實(shí)際上是求二叉樹每一層的最后一個節(jié)點(diǎn)，我們用DFS先遍歷右子樹并記錄遍歷的深度，如果這個右子節(jié)點(diǎn)的深度大于當(dāng)前所記錄的最大深度，說明它是下一層的最右節(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ù)雜度
時間 O(b^(h+1)-1) 空間 O(b^h) 對于二叉樹b=2
思路我們同樣可以借用層序遍歷的思路，只要每次把這一層的最后一個元素取出來就行了，具體代碼參見Binary Tree Traversal中的Binary Tree Level Order Traversal
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64469.html
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：遞歸法復(fù)雜度時間空間遞歸棧空間對于二叉樹思路簡單的二叉樹遍歷，遍歷的過程中記錄之前的路徑，一旦遍歷到葉子節(jié)點(diǎn)便將該路徑加入結(jié)果中。當(dāng)遇到最小公共祖先的時候便合并路徑。需要注意的是，我們要單獨(dú)處理目標(biāo)節(jié)點(diǎn)自身是最小公共祖先的情況。 Root To Leaf Binary Tree Paths Given a binary tree, return all root-to-leaf pat...
摘要：原題鏈接遞歸法復(fù)雜度時間空間遞歸?？臻g思路這個難倒大神的題也是非常經(jīng)典的一道測試對二叉樹遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點(diǎn)或葉子節(jié)點(diǎn)時，不再交換，直接返回該節(jié)點(diǎn)。代碼給出的是后序遍歷的自下而上的交換，先序遍歷的話就是自上而下的交換。 Invert Binary Tree Invert a binary tree. 4 / 2 7 / ...
LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹的最深深度。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 ...
閱讀 2300·2021-11-24 10:18
閱讀 2738·2021-11-19 09:59
閱讀 1722·2019-08-30 15:53
閱讀 1201·2019-08-30 15:53
閱讀 1079·2019-08-30 14:19
閱讀 2492·2019-08-30 13:14
閱讀 3025·2019-08-30 13:00
閱讀 1962·2019-08-30 11:11
