无线网络优化工程师,网站建设优化制作公司,手机网站适应屏幕,网站广告弹出来代码100道面试必会算法-32-二叉树右视图用栈实现队列
给定一个二叉树的 根节点 root#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。
示例 1: 输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2:
输入: [1,n…100道面试必会算法-32-二叉树右视图用栈实现队列
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
示例 1: 输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2:
输入: [1,null,3]
输出: [1,3]示例 3:
输入: []
输出: []解决思路
解决这个问题可以采用层序遍历二叉树的方式并在每一层中只记录最右侧的节点值。
解决方法
初始化首先初始化一个空列表 res 用于存储结果并确保给定的根节点不为空。层序遍历利用队列来实现层序遍历首先将根节点入队。遍历节点在每一层中记录当前层的节点数然后依次弹出队列中的节点。记录右视图每次弹出节点时检查该节点是否是当前层的最后一个节点如果是则将其值添加到结果列表中。入队子节点同时将弹出节点的左右子节点入队。返回结果最后返回结果列表 res。
代码实现
class Solution {// 定义函数用于获取二叉树的右视图public ListInteger rightSideView(TreeNode root) {// 初始化结果列表ListInteger res new ArrayList();// 如果根节点为空直接返回空结果列表if (root null)return res;// 初始化队列用于层序遍历二叉树LinkedListTreeNode queue new LinkedList();// 将根节点入队queue.push(root);// 开始循环遍历二叉树while (!queue.isEmpty()) {// 记录当前层的节点数int count queue.size();while (count 0) {// 弹出队首元素TreeNode node queue.poll();// 如果是当前层最后一个节点将其值加入结果列表if (count 1) {res.add(node.val);}// 将左子节点入队if (node.left ! null) {queue.offer(node.left);}// 将右子节点入队if (node.right ! null) {queue.offer(node.right);}count--;}}return res;}
}时间复杂度为 O(n)
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 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问题概述
需要设计一个队列的实现但是使用栈作为底层数据结构。具体来说需要实现 pushpoppeek 和 empty 四种操作。
解决思路
为了使用栈来实现队列可以使用两个栈一个用于存储队列元素另一个用于辅助操作。主要思路是保持一个栈始终为空当需要执行 pop 或 peek 操作时将所有元素从一个栈中弹出并压入另一个栈以保证队列顺序。
解决方法
初始化使用两个栈 A 和 B 分别用来存储队列元素和辅助操作。入队操作 (push)将元素压入栈 A相当于队尾入队。出队操作 (pop)首先调用 peek 方法获取队首元素然后从栈 B 中弹出栈顶元素相当于队首出队并返回队首元素。查看队首元素 (peek)如果栈 B 不为空直接返回栈 B 的栈顶元素否则如果栈 A 也为空说明队列为空返回 -1否则将栈 A 中的所有元素依次弹出并压入栈 B以实现队列元素的倒序然后返回栈 B 的栈顶元素。判断队列是否为空 (empty)当栈 A 和栈 B 都为空时说明队列为空。
class MyQueue {private StackInteger A; // 栈A用来存储队列元素private StackInteger B; // 栈B用来辅助操作public MyQueue() {Anew Stack(); // 初始化栈ABnew Stack(); // 初始化栈B}public void push(int x) {A.push(x); // 将元素压入栈A相当于队尾入队}public int pop() {int repeek(); // 获取栈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实现队列元素倒序}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都为空说明队列为空}
}
