/*
第11题
------------------------------------
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，
父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
*/
//July 2010/10/19
//此题思路，tree_star and i 在257、258楼，讲的很明白了。
//定义 一个 结构体
struct NODE
{
NODE* pLeft;
NODE* pRight;
int MaxLen;
int MaxRgt;
};
NODE* pRoot; //根节点
int MaxLength;
void traversal_MaxLen(NODE* pRoot)
{
if(pRoot == NULL)
{
return 0;
};
if(pRoot->pLeft == NULL)
{
pRoot->MaxLeft = 0;
}
else //若左子树不为空
{
int TempLen = 0;
if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight)
//左子树上的，某一节点，往左边大，还是往右边大
{
TempLen+=pRoot->pLeft->MaxLeft;
}
else
{
TempLen+=pRoot->pLeft->MaxRight;
}
pRoot->nMaxLeft = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pLeft);
//此处，加上递归
}
if(pRoot->pRigth == NULL)
{
pRoot->MaxRight = 0;
}
else //若右子树不为空
{
int TempLen = 0;
if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight)
//右子树上的，某一节点，往左边大，还是往右边大
{
TempLen+=pRoot->pRight->MaxLeft;
}
else
{
TempLen+=pRoot->pRight->MaxRight;
}
pRoot->MaxRight = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pRight);
//此处，加上递归
}
if(pRoot->MaxLeft + pRoot->MaxRight > 0)
{
MaxLength=MaxLeft + MaxRight;
}
}
/*
第12题
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字
以及条件判断语句（A?B:C）。
*/
//July、2010/10/19
/*-----------------
循环只是让相同的代码执行n遍而已，我们完全可以不用for和while达到这个效果。
比如定义一个类，我们new一含有n个这种类型元素的数组，
那么该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。
------------------*/
#include <iostream.h>
class Temp
{
public:
Temp()
{
++N;
Sum += N;
}
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n]; //就是这个意思，new出n个数组。
delete []a;
a = 0;
return Temp::GetSum();
}
int main()
{
cout<<solution1_Sum(100)<<endl;
return 0;
}
//运行结果：
//5050
//Press any key to continue
/*
第13题：
题目：
输入一个单向链表，输出该链表中倒数第k个结点,
链表的倒数第0个结点为链表的尾指针。
*/
//此题一出，相信，稍微有点 经验的同志，都会说到：
/*------------------------
设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔k个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第k个节点了
-------------------------*/
//July、2010/10/19
//好了，请你指出 下述代码的错误?：
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
char data;
ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;
int fun(ListNode *head,int k)
{
pone = ptwo = head;
for(int i=0;i<=k;i++)
ptwo=ptwo->next;
while(ptwo!=NULL)
{
pone=pone->next;
ptwo=ptwo->next;
}
return pone->data;
}
int main()
{
char c;
head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
p = head;
c = getchar();
while(c !='0')
{
q = (ListNode*)malloc(sizeof(ListNode));
q->data = c;
q->next = NULL;
p->next = q;
p = p->next;
c = getchar();
}
cout<<"---------------"<<endl;
cout<<fun(head,2)<<endl;
return 0;
}
/*
第14题：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。
如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
*/
//由于数组已经过升序排列，所以，难度下降了不少。
//July、2010/10/19
#include <iostream.h>
bool FindTwoNumbersWithSum
(
int data[], // 已经排序的 数组
unsigned int length, // 数组长度
int sum, //用户输入的 sum
int& num1, // 输出符合和等于sum的第一个数
int& num2 // 第二个数
)
{
bool found = false;
if(length < 1)
return found;
int begin = 0;
int end = length - 1;
while(end > begin)
{
long curSum = data[begin] + data[end];
if(curSum == sum)
{
num1 = data[begin];
num2 = data[end];
found = true;
break;
}
else if(curSum > sum)
end--;
else
begin++;
}
return found;
}
int main()
{
int x,y;
int a[6]={1,2,4,7,11,15};
if(FindTwoNumbersWithSum(a,6,15,x,y) )
{
cout<<x<<endl<<y<<endl;
}
return 0;
}
/*-----------------
4
11
Press any key to continue
-----------------*/
//扩展：如果输入的数组是没有排序的，但知道里面数字的范围，其他条件不变，
//如何在O(n)时间里找到这两个数字？
/*
第15题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/ \ / \
5 7 9 11
输出：
8
/ \
10 6
/ \ / \
11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
*/
//就是递归 翻转树，有子树则递归翻转子树。
//July、2010/10/19
void Revertsetree(list *root)
{
if(!root)
return;
list *p;
p=root->leftch;
root->leftch=root->rightch;
root->rightch=p;
if(root->leftch)
Revertsetree(root->leftch);
if(root->rightch)
Revertsetree(root->rightch);
}