100道面试必会算法-32-二叉树右视图&用栈实现队列

100道面试必会算法-32-二叉树右视图&用栈实现队列

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

解决思路

解决这个问题，可以采用层序遍历二叉树的方式，并在每一层中只记录最右侧的节点值。

解决方法

1. 初始化：首先初始化一个空列表 res 用于存储结果，并确保给定的根节点不为空。
2. 层序遍历：利用队列来实现层序遍历，首先将根节点入队。
3. 遍历节点：在每一层中，记录当前层的节点数，然后依次弹出队列中的节点。
4. 记录右视图：每次弹出节点时，检查该节点是否是当前层的最后一个节点，如果是，则将其值添加到结果列表中。
5. 入队子节点：同时，将弹出节点的左右子节点入队。
6. 返回结果：最后返回结果列表 res。

代码实现

class Solution {
    // 定义函数，用于获取二叉树的右视图
    public List<Integer> rightSideView(TreeNode root) {
        // 初始化结果列表
        List<Integer> res = new ArrayList<>();
        // 如果根节点为空，直接返回空结果列表
        if (root == null)
            return res;
        // 初始化队列，用于层序遍历二叉树
        LinkedList<TreeNode> 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

问题概述

需要设计一个队列的实现，但是使用栈作为底层数据结构。具体来说，需要实现 push，pop，peek 和 empty 四种操作。

解决思路

为了使用栈来实现队列，可以使用两个栈，一个用于存储队列元素，另一个用于辅助操作。主要思路是保持一个栈始终为空，当需要执行 pop 或 peek 操作时，将所有元素从一个栈中弹出并压入另一个栈，以保证队列顺序。

解决方法

1. 初始化：使用两个栈 A 和 B 分别用来存储队列元素和辅助操作。
2. 入队操作 (push)：将元素压入栈 A，相当于队尾入队。
3. 出队操作 (pop)：首先调用 peek 方法获取队首元素，然后从栈 B 中弹出栈顶元素，相当于队首出队，并返回队首元素。
4. 查看队首元素 (peek)：如果栈 B 不为空，直接返回栈 B 的栈顶元素；否则，如果栈 A 也为空，说明队列为空，返回 -1；否则，将栈 A 中的所有元素依次弹出并压入栈 B，以实现队列元素的倒序，然后返回栈 B 的栈顶元素。
5. 判断队列是否为空 (empty)：当栈 A 和栈 B 都为空时，说明队列为空。

class MyQueue {
private Stack<Integer> A; // 栈A用来存储队列元素
private Stack<Integer> B; // 栈B用来辅助操作
public MyQueue() {
A=new Stack<>(); // 初始化栈A
B=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也为空，说明队列为空，返回-1
while(!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都为空，说明队列为空
}
}