資訊專欄INFORMATION COLUMN
Problem
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.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/
2 3 <---
5 4 <---
Solution - BFS
class Solution {
public List rightSideView(TreeNode root) {
//save into stack in level order
List res = new ArrayList<>();
if (root == null) return res;
Deque queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
if (i == size-1) res.add(cur.val);
}
}
return res;
}
}
Solution - DFS
class Solution {
public List rightSideView(TreeNode root) {
List res = new ArrayList<>();
if (root == null) return res;
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode root, int level, List res) {
if (root == null) return;
if (res.size() == level) res.add(root.val);
dfs(root.right, level+1, res);
dfs(root.left, level+1, res);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/72362.html
摘要：問題解答核心思想是每一層只取一個結(jié)點(diǎn)，所以的大小與高度是一樣的。 問題：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:Giv...
摘要：代碼層序遍歷復(fù)雜度時間空間對于二叉樹思路我們同樣可以借用層序遍歷的思路，只要每次把這一層的最后一個元素取出來就行了，具體代碼參見中的 Binary Tree Right Side View Given a binary tree, imagine yourself standing on the right side of it, return the values of the n...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：題意從一顆二叉樹轉(zhuǎn)為帶括號的字符串。這題是的姊妹題型，該題目的解法在這里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...
摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋?？蠢?，樹的左邊最深的底層是，是新的。對于每個，將鏈接右孩子的指針去掉，將變?yōu)楫?dāng)前左孩子的，成為左孩子的。遞歸的寫法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...
閱讀 3087·2023-04-25 20:43
閱讀 1724·2021-09-30 09:54
閱讀 1596·2021-09-24 09:47
閱讀 2881·2021-09-06 15:02
閱讀 3517·2021-02-22 17:09
閱讀 1239·2019-08-30 15:53
閱讀 1447·2019-08-29 17:04
閱讀 1965·2019-08-28 18:22
