最小数栈
描述
定义一个栈，操作有pop，push和min。
思路：
求栈的最小值，仅仅加入一个变量是不够的，因为弹出当前最小值后，还要记录次最小值。所以需要一个辅助栈。当压入的值小于当前最小值时，同时把他压入辅助栈，否则，再把当前的最小值压入辅助栈。
代码：
#include<stack>
using namespace std;
//要加std或者std::stack
struct MyStack
{
stack<int> s;
stack<int> min;
};
MyStack Stackpush(MyStack ms ,int v)
{
ms.s.push(v);
if (ms.min.size() == 0 || ms.min.top() > v)
ms.min.push(v);
else
{
ms.min.push(ms.min.top());
}
return ms;
}
MyStack Stackpop(MyStack ms)
{
assert(ms.s.size() > 0 && ms.min.size() > 0);
ms.s.pop();
ms.min.pop();
return ms;
}
int StackMin(MyStack ms)
{
if (ms.min.size() == 0)
return NULL;
return ms.min.top();
}
层次遍历
思路：
不同于其他遍历方式，遍历完一个节点后，需要再遍历右方的节点，需要记录上一层的节点，用队列来记录，每次遍历一个节点，将它的儿子节点入队。每次从队列中取出一个节点入队。
PS:广度遍历也是这个思路
代码：
void RankOrder(TreeNode* root)
{
deque<TreeNode*> q;
if (root == NULL)
return;
else
{
q.push_back(root);
}
while (q.size() != 0)
{
TreeNode* temp = q.front();
cout << temp->v;
q.pop_front();
if (temp->left != NULL)
q.push_back(temp->left);
if (temp->right != NULL)
q.push_back(temp->right);
}
}
后序遍历序列
描述：
给定一个序列，判断是否是某棵二叉搜索树。
思路：
二叉搜索树的特性是左子树的节点都小于根，右子树的节点都大于根。序列最后的数是根，第一段是左子树，第二段是右子树，当右子树出现小于根的树时，返回false，否则递归地对子序列判断。
代码：
bool BSTpostorder(int arr[], int len)
{
if (arr == NULL || len <= 0)
return false;
int root = arr[len - 1];
int i = 0;
for (; i < len - 1; i++)
{
if (arr[i] > root)
break;
}
int j = i;
for (; j < len - 1; j++)
{
if (arr[j] < root)
return false;
}
bool left = true;
if(i>0)//i==0，说明没有当前节点左子树
left = BSTpostorder(arr, i);
bool right = true;
if(i<len-1)//i==len-1，说明没有右子树
right = BSTpostorder(arr + i, len - 1 - i);
if (left && right)
return true;
}