第11题树文档格式.docx
《第11题树文档格式.docx》由会员分享，可在线阅读，更多相关《第11题树文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
{
16.
return
0;
17.
};
18.
19.
if（pRoot->
pLeft
20.
21.
pRoot->
MaxLeft
=
22.
}
23.
else
//若左子树不为空
24.
25.
TempLen
26.
pLeft->
>
MaxRight）
27.
//左子树上的，某一节点，往左边大，还是往右边大
28.
29.
TempLen+=pRoot->
MaxLeft;
30.
31.
32.
33.
MaxRight;
34.
35.
nMaxLeft
+
1;
36.
pLeft）;
37.
//此处，加上递归
38.
39.
pRigth
40.
41.
MaxRight
42.
43.
//若右子树不为空
44.
45.
46.
pRight->
47.
//右子树上的，某一节点，往左边大，还是往右边大
48.
49.
50.
51.
52.
53.
54.
55.
56.
pRight）;
57.
58.
59.
60.
0）
61.
62.
MaxLength=pRoot->
63.
64.}
Sorehead：
十一题我写了一个非递规的方法，一方面是非递规并不复杂，另外一方面我不大喜欢楼主答案中采用全局变量的方式，我一直认为全局变量能少就少，最好不用。
写的代码，如下：
1.typedef
struct
_tree
2.{
3.
key;
*left;
*right;
height_left;
height_right;
8.}
tree;
9.
10.#define
TREE_HEIGHT
32
12.int
get_tree_max_distance（tree
*head）
tree
*stack_node[TREE_HEIGHT];
stack_flag[TREE_HEIGHT];
top;
*node;
max_len;
if
（head
max_len
top
stack_node[top]
head;
stack_flag[top]
while
（top
!
-1）
node
stack_node[top];
（node
top--;
continue;
（stack_flag[top]
stack_flag[top]++;
stack_node[++top]
node->
left;
1）
right;
（node->
left
height_left
left->
height_right
?
1
:
right
right->
（max_len
<
height_right）
64.
65.
66.}
一次遍历，由于必须是后序遍历，因此加了一个flag数组用于保存栈中节点的状态：
0表示该节点刚开始处理；
1表示其左子树遍历完毕；
2表示右子树遍历完毕。
当然可以创建一个结构把节点地址和这个标志放在一起。
树的前序遍历和中序遍历并不需要这个标志，所以只需要一个栈保存节点地址即可。
非递归的方法，也可以如azuryy所示，这么写：
1.struct
Node
bool
_visited;
Node*
maxLeft;
8.
maxRight;
10.
Node（）
12.
_visited
false;
13.
maxLeft
maxRight
NULL;
18.};
20.int
maxLen
22.stack<
Node*>
nodeStack;
24.void
findMaxLen（
root
）
25.{
node;
（
NULL
;
nodeStack.push（
）;
while（
nodeStack.empty（））
nodeStack.top（）;
&
nodeStack.pop（）;
true;
max（
maxLeft,node->
||
66.
67.
（（
））
68.
69.
maxLen,
70.
71.
72.
73.
74.}
--------------------------------------------------------
思路改进：
计算一个二叉树的最大距离有两个情况:
*情况A:
通过根节点，路径经过左子树的最深节点，再到右子树的最深节点。
*情况B:
不通过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。
有人评价原书上的代码时，说：
书上的代码有几个缺点:
1.算法加入侵入式（intrusive）的资料nMaxLeft,nMaxRight
2.使用全局变量nMaxLen。
每次使用要额外初始化。
而且就算是不同的独立资料，也不能在多个线程使用这个函数
3.逻辑比较复杂，也有许多NULL相关的条件测试。
于是给出了下述改进代码：
1.RESULT
GetMaximumDistance（NODE*
root）
（!
RESULT
empty
0,
-1
//
trick:
nMaxDepth
is
and
then
caller
will
plus
to
balance
it
as
zero.
empty;
lhs
GetMaximumDistance（root->
rhs
result;
//nMaxDepth
就是左子树或右子树的深度加1；
result.nMaxDepth
max（lhs.nMaxDepth
1,
rhs.nMaxDepth
1）;
//nMaxDistance
则取A和B情况的最大值。
result.nMaxDistance
max（max（lhs.nMaxDistance,
rhs.nMaxDistance）,
lhs.nMaxDepth
2）;
//B：
不通过根节点时，取左右子树中最大距离的大值，A：
通过根节点，左+右+2.
24.}
第12题（语法）
题目：
求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?
B:
C）。
说实话，我比较反感这种题目，这不是什么算法，就是一些纯技巧方面的东西，有点像我们很多考试的题目，根本就不能代表什么。
刚看到这个题目，我的第一想法就是多半只能用递规解决，接下来难点就是递规如何结束。
题目的要求是比较苛刻的，楼主答案里面用的两种方法确实挺巧妙的，但我不会C++，因此只能另外想办法。
下面是我写的代码：
intsum（intn）
{
intval=0;
n>
0&
（val=n+sum（n-1））;
returnval;
}
虽然功能是实现了，但这个代码编译时是有警告的，当然这个警告不重要。
但我总觉得有更加合适的方法。
或者如leeyunce所说：
思路：
模板元编程，最快捷的计算方式，编译期完成计算
#include<
iostream>
usingnamespacestd;
template<
intN>
structCalCls
enum{sum=CalCls<
N-1>
sum+N};
structCalCls<
0>
enum{sum=0};
intmain（）
cout<
"
1+2+3+...+100="
CalCls<
100>
sum<
endl;
return0;
另，一位兄台，短短三行代码想解决第12题，是否正确列?
：
return（（n*（n+1））>
第13题（链表）：
输入一个单向链表，输出该链表中倒数第k个结点。
链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
structListNode
intm_nKey;
ListNode*m_pNext;
思路和楼主一致，下面是我写的代码，只是判断上多一些。
list*list_find_desc（list*head,intk）
{
list*p,*q;
if（head==NULL||k<
0）
returnNULL;
p=head;
while（p!
=NULL&
k-->
=0）
p=p->
next;
}
if（p==NULL）
returnk<
0?
head:
NULL;
q=head;
=NULL）
q=q->
returnq;
第14题（数组）：
输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O（n）。
如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。
由于4+11=15，因此输出4和11。
思路和楼主一致，这个题目比较简单，尤其是还排好序。
楼主提供的另外一个思路也挺好，我还真没想到。
他说的是指以下这个思路：
2.第14题，还有一种思路，如下俩个数组：
1、2、
4、7、11、15
//用15减一下为
14、13、11、8、4、0
//如果下面出现了和上面一样的数，稍加判断，就能找出这俩个数来了。
第一个数组向右扫描，第二个数组向左扫描。
第15题（树）：
输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
//
610
////
57911
输出：
升级会员 