21. 栈的压入、弹出序列
- 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
// Solution:如果下一个弹出的数字是栈顶数字，直接弹出；
// 如果下一个弹出的数字不在栈顶，继续入栈，直到把该数字压入栈顶；
// 如果所有数字都入栈，还未找到该数字，那么该序列不可能是弹出序列
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
bool bPossible = false;
int pushVSize = pushV.size();
int popVSize = popV.size();
if (pushVSize == 0 || popVSize == 0) {
return bPossible;
}
stack<int> stack_data;
int pushi = 0, popi = 0;
while (popi < popVSize) { // 遍历完popV，表示找到了该序列
while (stack_data.empty() || stack_data.top() != popV[popi]) {
if (pushi >= pushVSize) {// 没有找到该数字
break;
}
stack_data.push(pushV[pushi]);
pushi ++;
}
if (stack_data.top() == popV[popi]) {
stack_data.pop();
popi ++;
} else { // 栈顶元素仍不是该数字
break;
}
}
if (popi == popVSize) {
bPossible = true;
}
return bPossible;
}
};
22. 从上往下打印二叉树
- 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
// Solution：使用队列
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if (root == NULL) {
return res;
}
queue<TreeNode *> treeQueue;
treeQueue.push(root);
while (treeQueue.size() != 0) {
TreeNode* node = treeQueue.front();
treeQueue.pop();
res.push_back(node->val);
if (node->left != NULL) {
treeQueue.push(node->left);
}
if (node->right != NULL) {
treeQueue.push(node->right);
}
}
return res;
}
};
23. 二叉搜索树的后序遍历序列（搜索树，左子树<根节点<右子树）
- 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
// Solution:先找根节点，区分左子树&右子树，递归重构树
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int len = sequence.size();
if (len == 0) {
return false;
}
int root = sequence[len-1];
vector<int> leftT, rightT;
// 确定左子树范围
int index = 0;
for (; index < len-1; index ++) {
if (sequence[index] > root) {
break;
}
leftT.push_back(sequence[index]);
}
// 确认右子树值都大于root
int i = index;
for (; i < len-1; i ++) {
if (sequence[i] <= root) {
return false;
}
rightT.push_back(sequence[i]);
}
bool leftIsTree = true;
bool rightIsTree = true;
if (leftT.size()>1) {// 有左子树，检查其是否满足二叉搜索树
leftIsTree = VerifySquenceOfBST(leftT);
}
if (rightT.size()>1) {// 有右子树，检查其是否满足二叉搜索树
rightIsTree = VerifySquenceOfBST(rightT);
}
return (leftIsTree && rightIsTree);
}
};
24. 二叉树中和为某一值的路径
- 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
// Solution: 递归入栈，从根节点到叶节点和等于预期和，作为一个路径
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int> > result;
vector<int> path;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if (root == NULL) {
return result;
}
path.push_back(root->val);
// 是叶节点并且达到预期和
if (root->left == NULL && root->right == NULL && expectNumber-root->val == 0) {
result.push_back(path);
}
// 有左子树
if (root->left != NULL) {
FindPath(root->left, expectNumber-root->val);
}
// 有右子树
if (root->right != NULL) {
FindPath(root->right, expectNumber-root->val);
}
path.pop_back();
return result;
}
};
25. 复杂链表的复制【分治法-递归实现】
- 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
// Solution:
//X (1)先next，后random——每次查找都要用s步，平均用时O(n),n个结点时间复杂度O(n^2);
//X (2)先next，后random，每个结点N创建N’，哈希表存放<N,N'>，空间O(n)，时间O(n);
//√ (3)每个结点N后创建对应N'，S->next结点即为S'，∴N'链接S'，将链表奇数位置、偶数位置拆分，时间O(n).
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
CloneNodes(pHead);
ConnectRandomNodes(pHead);
return SplitNodes(pHead);
}
void CloneNodes(RandomListNode* pHead) { // 每个结点N后创建对应N'
RandomListNode* pNode = pHead;
while (pNode != NULL) {
RandomListNode* pCloned = new RandomListNode(pNode->label);
pCloned->next = pNode->next;
pCloned->random = NULL;
pNode->next = pCloned;
pNode = pCloned->next;
}
}
void ConnectRandomNodes(RandomListNode* pHead) { // S->next结点即为S'，∴N'链接S'
RandomListNode* pNode = pHead;
while (pNode != NULL) {
RandomListNode* pNCloned = pNode->next;
if (pNode->random != NULL) { // Tip:避免空指针访问
pNCloned->random = pNode->random->next;
}
pNode = pNCloned->next;
}
}
RandomListNode* SplitNodes(RandomListNode* pHead) {
RandomListNode* pNode = pHead;
RandomListNode* pClonedHead = NULL;
RandomListNode* pClonedNode = NULL;
if (pNode != NULL) { // 头节点复制
pClonedHead = pHead->next;
pClonedNode = pNode->next;
pNode->next = pClonedNode->next;
pNode = pNode->next;
}
while (pNode != NULL) {
pClonedNode->next = pNode->next;
pClonedNode = pClonedNode->next;
pNode->next = pClonedNode->next;
pNode = pNode->next;
}
return pClonedHead;
}
};
