这里沿用传统二叉查找树(BST)的概念：所有左子树都小于根，右子树都大于根。(不止是直接孩子，还有间接孩子！)

现在给出一个整数序列，要求判断它是否是一棵二叉查找树BST的后序遍历结果。

如果去掉BST这个条件，我们一般是不能只根据后序遍历结果来确定某一棵树的。

有了BST这个条件后，我们可以这么做：

定义如下递归函数头：
int judge(int* arr, int start, int end)
(1)另root = end-1，则arr[root]为从star[......]

继续阅读

链表定义如下：
struct Node
{
struct Node* next;
int data;
};
非递归反置链表如下：
struct Node* ll_reverse(struct Node* head)
{
if(head==NULL)
{
return NULL;
}
else
{
struct Node* pre = NULL;
struct Node* next = NULL;
struct Node* ptr =[......]

继续阅读

编程之美上的一道题。

给出两个单向链表的头指针，比如h1和h2，判断这两个链表是否相交。先假设链表不带环。

首先对于“链表相交”这个概念，要澄清一下，不是单点相交，而是如下这种：

其实也很好理解，相交在平面几何里面的概念是点重合。那么对于链表中某个结点重合，必然next指针也是一样的，于是就是上面这个样子了。

思路：如上分析后就很简单了，如果相交，那么肯定从h1找到尾部(NULL的前一个)和好

找到的尾部是重合的。如果不重合，肯定不相交，是重要条件。

代码如下[......]

继续阅读

有许多问题，可以利用试探和回溯的搜索技术求解。

求解的过程实际是先序遍历一棵“状态树”的过程。

例1：有集合A = {1, 2, ...n}，求A的全部子集。

思路：从求全部子集（幂集）这个事情上，实际上对每个元素只有两个状态：要么在一个子集中，要么不在。

因此，可以逐一对A中每个元素进行“取”和“舍”，从而构造一棵完全二叉树。

算法如下：

注意这里是1~n，不是0~n
void mj(int n, int pos, int* flag)
{
    i[......]

继续阅读