俄羅斯做貨代的網(wǎng)站公司網(wǎng)站設計哪家好
100道面試必會算法-32-二叉樹右視圖&用棧實現(xiàn)隊列
給定一個二叉樹的 根節(jié)點 root
,想象自己站在它的右側(cè),按照從頂部到底部的順序,返回從右側(cè)所能看到的節(jié)點值。
示例 1:
輸入: [1,2,3,null,5,null,4]
輸出: [1,3,4]
示例 2:
輸入: [1,null,3]
輸出: [1,3]
示例 3:
輸入: []
輸出: []
解決思路
解決這個問題,可以采用層序遍歷二叉樹的方式,并在每一層中只記錄最右側(cè)的節(jié)點值。
解決方法
- 初始化:首先初始化一個空列表
res
用于存儲結(jié)果,并確保給定的根節(jié)點不為空。 - 層序遍歷:利用隊列來實現(xiàn)層序遍歷,首先將根節(jié)點入隊。
- 遍歷節(jié)點:在每一層中,記錄當前層的節(jié)點數(shù),然后依次彈出隊列中的節(jié)點。
- 記錄右視圖:每次彈出節(jié)點時,檢查該節(jié)點是否是當前層的最后一個節(jié)點,如果是,則將其值添加到結(jié)果列表中。
- 入隊子節(jié)點:同時,將彈出節(jié)點的左右子節(jié)點入隊。
- 返回結(jié)果:最后返回結(jié)果列表
res
。
代碼實現(xiàn)
class Solution {// 定義函數(shù),用于獲取二叉樹的右視圖public List<Integer> rightSideView(TreeNode root) {// 初始化結(jié)果列表List<Integer> res = new ArrayList<>();// 如果根節(jié)點為空,直接返回空結(jié)果列表if (root == null)return res;// 初始化隊列,用于層序遍歷二叉樹LinkedList<TreeNode> queue = new LinkedList();// 將根節(jié)點入隊queue.push(root);// 開始循環(huán)遍歷二叉樹while (!queue.isEmpty()) {// 記錄當前層的節(jié)點數(shù)int count = queue.size();while (count > 0) {// 彈出隊首元素TreeNode node = queue.poll();// 如果是當前層最后一個節(jié)點,將其值加入結(jié)果列表if (count == 1) {res.add(node.val);}// 將左子節(jié)點入隊if (node.left != null) {queue.offer(node.left);}// 將右子節(jié)點入隊if (node.right != null) {queue.offer(node.right);}count--;}}return res;}
}
時間復雜度為 O(n)
用棧實現(xiàn)隊列
請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應當支持一般隊列支持的所有操作(push
、pop
、peek
、empty
):
實現(xiàn) MyQueue
類:
void push(int x)
將元素 x 推到隊列的末尾int pop()
從隊列的開頭移除并返回元素int peek()
返回隊列開頭的元素boolean empty()
如果隊列為空,返回true
;否則,返回false
說明:
- 你 只能 使用標準的棧操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。 - 你所使用的語言也許不支持棧。你可以使用 list 或者 deque(雙端隊列)來模擬一個棧,只要是標準的棧操作即可。
示例 1:
輸入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出:
[null, null, null, 1, 1, false]解釋:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
問題概述
需要設計一個隊列的實現(xiàn),但是使用棧作為底層數(shù)據(jù)結(jié)構(gòu)。具體來說,需要實現(xiàn) push
,pop
,peek
和 empty
四種操作。
解決思路
為了使用棧來實現(xiàn)隊列,可以使用兩個棧,一個用于存儲隊列元素,另一個用于輔助操作。主要思路是保持一個棧始終為空,當需要執(zhí)行 pop
或 peek
操作時,將所有元素從一個棧中彈出并壓入另一個棧,以保證隊列順序。
解決方法
- 初始化:使用兩個棧
A
和B
分別用來存儲隊列元素和輔助操作。 - 入隊操作 (push):將元素壓入棧
A
,相當于隊尾入隊。 - 出隊操作 (pop):首先調(diào)用
peek
方法獲取隊首元素,然后從棧B
中彈出棧頂元素,相當于隊首出隊,并返回隊首元素。 - 查看隊首元素 (peek):如果棧
B
不為空,直接返回棧B
的棧頂元素;否則,如果棧A
也為空,說明隊列為空,返回 -1;否則,將棧A
中的所有元素依次彈出并壓入棧B
,以實現(xiàn)隊列元素的倒序,然后返回棧B
的棧頂元素。 - 判斷隊列是否為空 (empty):當棧
A
和棧B
都為空時,說明隊列為空。
class MyQueue {private Stack<Integer> A; // 棧A用來存儲隊列元素private Stack<Integer> B; // 棧B用來輔助操作public MyQueue() {A=new Stack<>(); // 初始化棧AB=new Stack<>(); // 初始化棧B}public void push(int x) {A.push(x); // 將元素壓入棧A,相當于隊尾入隊}public int pop() {int re=peek(); // 獲取棧B的棧頂元素,即隊首元素B.pop(); // 彈出棧B的棧頂元素,相當于隊首出隊return re; // 返回隊首元素}public int peek() {if(!B.isEmpty()) return B.peek(); // 如果棧B不為空,則直接返回棧B的棧頂元素if(A.isEmpty()) return -1; // 如果棧A也為空,說明隊列為空,返回-1while(!A.isEmpty()){B.push(A.pop()); // 將棧A中的元素依次彈出并壓入棧B,實現(xiàn)隊列元素倒序}return B.peek(); // 返回棧B的棧頂元素,即隊首元素}public boolean empty() {return A.isEmpty() && B.isEmpty(); // 如果棧A和棧B都為空,說明隊列為空}
}}return B.peek(); // 返回棧B的棧頂元素,即隊首元素}public boolean empty() {return A.isEmpty() && B.isEmpty(); // 如果棧A和棧B都為空,說明隊列為空}
}