目录

验证栈序列（medium）

题目解析

讲解算法原理

编写代码

N叉树的层序遍历（medium）

题目解析

讲解算法原理

编写代码

---

验证栈序列（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进⾏的推⼊push和弹出pop操作序列的结果时，返回 true ；否则，返回 false 。

⽰例1：
输⼊：pushed=[1,2,3,4,5],popped=[4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执⾏：
push(1),push(2),push(3),push(4),pop()->4,
push(5),pop()->5,pop()->3,pop()->2,pop()->1
⽰例2：
输⼊：pushed=[1,2,3,4,5],popped=[4,3,5,1,2]
输出：false
解释：1不能在2之前弹出。

提⽰：
◦ 1 <= pushed.length <= 1000
◦ 0 <= pushed[i] <= 1000
◦ pushed 的所有元素互不相同
◦ popped.length == pushed.length
◦ popped 是 pushed 的⼀个排列

讲解算法原理

解法（栈）：
算法思路：
⽤栈来模拟进出栈的流程。
⼀直让元素进栈，进栈的同时判断是否需要出栈。当所有元素模拟完毕之后，如果栈中还有元素，那么就是⼀个⾮法的序列。否则，就是⼀个合法的序列。

编写代码

c++算法代码：

class Solution
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i = 0, n = popped.size();for(auto x : pushed){st.push(x);while(st.size() && st.top() == popped[i]){st.pop();i++;}}return i == n;}
};

java算法代码：

class Solution
{public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> st = new Stack<>();int i = 0, n = popped.length;for(int x : pushed){st.push(x);while(!st.isEmpty() && st.peek() == popped[i]){st.pop();i++;}}return i == n;}
}

N叉树的层序遍历（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个N叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输⼊是⽤层序遍历，每组⼦节点都由null值分隔（参⻅⽰例）。
⽰例1：

输⼊：root=[1,null,3,2,4,null,5,6]输出：[[1],[3,2,4],[5,6]]
⽰例2：

输⼊：root=[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提⽰：
◦ 树的⾼度不会超过 1000 ◦ 树的节点总数在 [0, 10^4] 之间

讲解算法原理

解法：
算法思路：
层序遍历即可~
仅需多加⼀个变量，⽤来记录每⼀层结点的个数就好了。

编写代码

c++算法代码：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/
class Solution
{
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret; // 记录最终结果 queue<Node*> q; // 层序遍历需要的队列if(root == nullptr) return ret;q.push(root);while(q.size()){int sz = q.size(); // 先求出本层元素的个数 vector<int> tmp; // 统计本层的节点for(int i = 0; i < sz; i++){Node* t = q.front();q.pop();tmp.push_back(t->val); for(Node* child : t->children) // 让下⼀层结点⼊队 {if(child != nullptr)q.push(child);}}ret.push_back(tmp);}return ret;}
};

java算法代码：

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/
class Solution
{public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ret = new ArrayList<>();if(root == null) return ret;Queue<Node> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int sz = q.size();List<Integer> tmp = new ArrayList<>(); // 统计本层的结点信息 for(int i = 0; i < sz; i++){Node t = q.poll();tmp.add(t.val);for(Node child : t.children) // 让孩⼦⼊队 {if(child != null)q.add(child);}}ret.add(tmp);}return ret;}
}