难度中等100
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
1
2
3
4
5
| 输入：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：
1
2
3
| 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
|
用辅助栈来模拟入栈和出栈的操作，对入栈序列，每次入栈一个，之后循环判断栈顶元素和当前出栈序列的元素是否相等，若相等，就出栈，并使出栈序列下标递增。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> sim;
int k = 0;
for(int i = 0; i < pushed.size(); ++i)
{
sim.push(pushed[i]);
while(!sim.empty() && sim.top() == popped[k])
{
++k;
sim.pop();
}
}
return sim.empty();
}
};
|
难度中等52
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回：
提示：
节点总数 <= 1000
层序遍历树，用队列辅助，没啥可说的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if(root == nullptr) return {};
queue<TreeNode*> q;
q.push(root);
TreeNode* temp = nullptr;
while(!q.empty())
{
temp = q.front();
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
res.push_back(temp->val);
q.pop();
}
return res;
}
};
|
难度简单
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
提示：
节点总数 <= 1000
自己搞了一个使用两个栈的做法，忘记了可以用q.size()了。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) return {};
queue<TreeNode*> q1;
queue<TreeNode*> q2;
q1.push(root);
TreeNode* temp = nullptr;
vector<int> tempRes;
while(!q1.empty() || !q2.empty())
{
while(!q1.empty())
{
temp = q1.front();
if(temp->left) q2.push(temp->left);
if(temp->right) q2.push(temp->right);
tempRes.push_back(temp->val);
q1.pop();
}
while(!q2.empty())
{
q1.push(q2.front());
q2.pop();
}
res.push_back(tempRes);
tempRes.clear();
}
return res;
}
};
|
使用一个栈的做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) return {};
queue<TreeNode*> q1;
q1.push(root);
TreeNode* temp = nullptr;
while(!q1.empty())
{
vector<int> tempRes;
int n = q1.size();
for(int i = 0; i < n; ++i)
{
temp = q1.front();
q1.pop();
tempRes.push_back(temp->val);
if(temp->left) q1.push(temp->left);
if(temp->right) q1.push(temp->right);
}
res.push_back(tempRes);
}
return res;
}
};
|
难度中等58
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[20,9],
[15,7]
]
|
提示：
节点总数 <= 1000
还是层序遍历，使用双端队列，奇数层前取后放(左→右)，偶数层后取前放(右→左)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) return res;
bool flag = true;
deque<TreeNode*> dq;
dq.push_back(root);
while(!dq.empty())
{
int n = dq.size();
vector<int> tempRes;
TreeNode* temp;
if(flag)
{
for(int i = 0; i < n; ++i)
{
temp = dq.front();
dq.pop_front();
if(temp->left) dq.push_back(temp->left);
if(temp->right) dq.push_back(temp->right);
tempRes.push_back(temp->val);
}
}
else
{
for(int i = 0; i < n; ++i)
{
temp = dq.back();
dq.pop_back();
if(temp->right) dq.push_front(temp->right);
if(temp->left) dq.push_front(temp->left);
tempRes.push_back(temp->val);
}
}
flag = !flag;
res.push_back(tempRes);
}
return res;
}
};
|
难度中等153
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
示例 1：
1
2
| 输入: [1,6,3,2,5]
输出: false
|
示例 2：
1
2
| 输入: [1,3,2,6,5]
输出: true
|
提示：
数组长度 <= 1000
要用递归的思想，最后一个是根节点，然后找到第一个大于根节点的，其后面是右子树，右子树均大于根，左子树均小于根，递归判断左子树和右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private:
bool DFS(int Start, int End, vector<int>& postorder) {
if(Start >= End) return true;
int Standard = postorder[End];
int Break = Start;
while(postorder[Break] < Standard) Break++;
for(int i = Break; i < End; i++) {
if(postorder[i] <= Standard) return false;
}
return DFS(Start, Break-1, postorder) && DFS(Break, End - 1, postorder);
}
public:
bool verifyPostorder(vector<int>& postorder) {
if(postorder.size() < 2) return true;
return DFS(0, postorder.size() - 1, postorder);
}
};
|
难度中等111
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
1
2
3
4
5
6
7
| 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
|
返回:
1
2
3
4
| [
[5,4,11,2],
[5,8,4,5]
]
|
提示：
节点总数 <= 10000
回溯的思想。满足条件的情况是，路径和为sum并且为叶子节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
private:
vector<vector<int> > res;
vector<int> temp;
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root) return {};
recursion(root, sum);
return res;
}
void recursion(TreeNode *root, int sum)
{
if(!root) return;
temp.push_back(root -> val);
sum -= root -> val;
if(sum == 0 && !root -> left && !root -> right)
res.push_back(temp);
recursion(root -> left, sum);
recursion(root -> right, sum);
temp.pop_back();
}
};
|
想了好久才明白，自己的方法是败在了剪枝上(天天想这么多还搞错了是真的蠢)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> path;
dfs(root, 0, res, path, sum);
return res;
}
void dfs(TreeNode* node, int tempSum, vector<vector<int>>& res, vector<int> path, int target)
{
if(node == nullptr){
return;
}
path.push_back(node->val);
tempSum += node->val;
if(node->left == nullptr && node->right == nullptr && tempSum == target){
res.push_back(path);
return;
}
else
{
dfs(node->left, tempSum, res, path, target);
dfs(node->right, tempSum, res, path, target);
tempSum -= node->val;
}
}
};
|
难度中等125
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
1
2
| 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
|
示例 2：
1
2
| 输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
|
示例 3：
1
2
| 输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
|
示例 4：
1
2
3
| 输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
|
这道题较为简单的一个思路是使用hash表记录老节点到新节点的映射，这一步是为了后面找random指针的指向而进行的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
unordered_map<Node*, Node*> randMap;
Node* newHead = new Node(head->val);
randMap[head] = newHead;
Node* cur = head;
Node* newCur = newHead;
cur = cur->next;
while(cur){
newCur->next = new Node(cur->val);
randMap[cur] = newCur->next;
cur = cur->next;
newCur = newCur->next;
}
cur = head;
newCur = newHead;
while(cur){
newCur->random = randMap[cur->random];
cur = cur->next;
newCur = newCur->next;
}
return newHead;
}
};
|
还有一种想法是在原链表上复制，这样不用记录在复制random指向的时候，可以在副本上完全拷贝。
1
| 1->2->3->null 变成了 1->1'->2->2'->3->3'->null
|
拷贝random的时候，直接新random = 原random->next，最后串联新链表，并且恢复旧链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL)return NULL;
Node*p=head,*q;
while(p){
q=p->next;
p->next=new Node(p->val);
p->next->next=q;
p=q;
}
p=head;
while(1){
if(p->random)
p->next->random=p->random->next;
if(p->next->next) p=p->next->next;
else break;
}
p=head;q=head->next;
Node *ret=head->next;
while(p&&q){
p->next=q->next;
p=p->next;
if(p)q->next=p->next;
else break;
q=q->next;
}
return ret;
}
};
|
