第11题树.docx

第11题树.docx

《第11题树.docx》由会员分享，可在线阅读，更多相关《第11题树.docx（24页珍藏版）》请在冰点文库上搜索。

第11题树

第11题（树）

求二叉树中节点的最大距离...

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，

我们姑且定义"距离"为两节点之间边的个数。

写一个程序，

求一棵二叉树中相距最远的两个节点之间的距离。

原先我给的答案，如下（个人感觉，还是本人写的代码更清晰）：

1.//定义一个结构体  

2.struct NODE  

3.{   

4.    NODE* pLeft;  

5.    NODE* pRight;  

6.    int MaxLen;  

7.    int MaxRgt;  

8.};    

9.NODE* pRoot;  //根节点  

10.int MaxLength;  

11.  

12.void traversal_MaxLen（NODE* pRoot）  

13.{  

14.    if（pRoot == NULL）  

15.    {  

16.        return 0;  

17.    };  

18.     

19.    if（pRoot->pLeft == NULL）     

20.    {  

21.        pRoot->MaxLeft = 0;  

22.    }  

23.    else                                 //若左子树不为空  

24.    {  

25.        int TempLen = 0;  

26.        if（pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight）  

27.          //左子树上的，某一节点，往左边大，还是往右边大  

28.        {  

29.            TempLen+=pRoot->pLeft->MaxLeft;  

30.        }  

31.        else  

32.        {  

33.            TempLen+=pRoot->pLeft->MaxRight;  

34.        }  

35.        pRoot->nMaxLeft = TempLen + 1;  

36.        traversal_MaxLen（NODE* pRoot->pLeft）;  

37.        //此处，加上递归  

38.    }    

39.    if（pRoot->pRigth == NULL）  

40.    {  

41.        pRoot->MaxRight = 0;  

42.    }  

43.    else                                //若右子树不为空  

44.    {  

45.        int TempLen = 0;  

46.        if（pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight）   

47.        //右子树上的，某一节点，往左边大，还是往右边大  

48.        {  

49.            TempLen+=pRoot->pRight->MaxLeft;  

50.        }  

51.        else  

52.        {  

53.            TempLen+=pRoot->pRight->MaxRight;  

54.        }  

55.        pRoot->MaxRight = TempLen + 1;  

56.        traversal_MaxLen（NODE* pRoot->pRight）;  

57.        //此处，加上递归  

58.    }  

59.     

60.   if（pRoot->MaxLeft + pRoot->MaxRight > 0）  

61.    {  

62.        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;  

63.    }  

64.}  

 Sorehead：

    十一题我写了一个非递规的方法，一方面是非递规并不复杂，另外一方面我不大喜欢楼主答案中采用全局变量的方式，我一直认为全局变量能少就少，最好不用。

写的代码，如下：

1.typedef struct _tree  

2.{  

3.        int             key;  

4.        struct _tree    *left;  

5.        struct _tree    *right;  

6.        int             height_left;  

7.        int             height_right;  

8.} tree;  

9.  

10.#define TREE_HEIGHT 32  

11.  

12.int get_tree_max_distance（tree *head）  

13.{  

14.        tree *stack_node[TREE_HEIGHT];  

15.        int stack_flag[TREE_HEIGHT];  

16.        int top;  

17.        tree *node;  

18.        int max_len;  

19.  

20.        if （head == NULL）  

21.                return 0;  

22.  

23.        max_len = 0;  

24.        top = 0;  

25.        stack_node[top] = head;  

26.        stack_flag[top] = 0;  

27.        while （top !

= -1）  

28.        {  

29.                node = stack_node[top];  

30.                if （node == NULL）  

31.                {  

32.                        top--;  

33.                        continue;  

34.                }  

35.  

36.                if （stack_flag[top] == 0）  

37.                {  

38.                        stack_flag[top]++;  

39.                        stack_node[++top] = node->left;  

40.                        stack_flag[top] = 0;  

41.                }  

42.                else if （stack_flag[top] == 1）  

43.                {  

44.                        stack_flag[top]++;  

45.                        stack_node[++top] = node->right;  

46.                        stack_flag[top] = 0;  

47.                }  

48.                else  

49.                {  

50.                        if （node->left !

= NULL）  

51.                                node->height_left = node->left->height_left > node->left->height_right ?

 node->left->height_left + 1 :

 node->left->height_right + 1;  

52.                        else  

53.                                node->height_left = 0;  

54.                        if （node->right !

= NULL）  

55.                                node->height_right = node->right->height_left > node->right->height_right ?

 node->right->height_left + 1 :

 node->right->height_right + 1;  

56.                        else  

57.                                node->height_right = 0;  

58.  

59.                        if （max_len < node->height_left + node->height_right）  

60.                                max_len = node->height_left + node->height_right;  

61.  

62.                        top--;  

63.                }  

64.        }  

65.        return max_len;  

66.}  

 一次遍历，由于必须是后序遍历，因此加了一个flag数组用于保存栈中节点的状态：

0表示该节点刚开始处理；1表示其左子树遍历完毕；2表示右子树遍历完毕。

当然可以创建一个结构把节点地址和这个标志放在一起。

   树的前序遍历和中序遍历并不需要这个标志，所以只需要一个栈保存节点地址即可。

非递归的方法，也可以如azuryy所示，这么写：

1.struct Node  

2.{  

3.    bool _visited;  

4.  

5.    Node* left;  

6.    Node* right;  

7.    int maxLeft;  

8.    int maxRight;  

9.  

10.    Node（）  

11.    {  

12.        _visited = false;  

13.        maxLeft = 0;  

14.        maxRight = 0;  

15.        left = NULL;  

16.        right = NULL;  

17.    }  

18.};  

19.  

20.int maxLen   = 0;  

21.  

22.stack nodeStack;  

23.  

24.void findMaxLen（ Node* root ）  

25.{  

26.    Node* node;  

27.  

28.    if （ root == NULL ）   

29.    {  

30.        return ;  

31.    }  

32.  

33.    nodeStack.push（ root ）;  

34.    while（ !

nodeStack.empty（））  

35.    {  

36.        node = nodeStack.top（）;  

37.  

38.        if （ node->left == NULL && node->right == NULL ）  

39.        {  

40.            nodeStack.pop（）;  

41.            node->_visited = true;  

42.            continue;  

43.        }  

44.        if （ node->left ）   

45.        {  

46.            if （ !

node->left->_visited ）  

47.            {  

48.                nodeStack.push（ node->left ） ;  

49.            }              

50.            else   

51.            {  

52.                node->maxLeft = max（ node->left->maxLeft,node->left->maxRight ） + 1;  

53.            }  

54.        }  

55.        if （ （ !

node->left || node->left->_visited ） && node->right ）  

56.        {  

57.            if （ !

node->right->_visited ）  

58.            {  

59.                nodeStack.push（ node->right ） ;  

60.            }              

61.            else   

62.            {  

63.                node->maxRight = max（ node->right->maxLeft,node->right->maxRight ） + 1;  

64.            }  

65.        }  

66.  

67.        if （（ !

node->left || node->left->_visited ） && （ !

node->right || node->right->_visited ））  

68.        {  

69.            maxLen = max（ maxLen, node->maxLeft + node->maxRight ）;  

70.            node->_visited = true;  

71.            nodeStack.pop（）;              

72.        }  

73.    }  

74.}  

--------------------------------------------------------

思路改进：

计算一个二叉树的最大距离有两个情况:

 *情况A:

通过根节点，路径经过左子树的最深节点，再到右子树的最深节点。

 *情况B:

不通过根节点，而是左子树或右子树的最大距离路径，取其大者。

只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

有人评价原书上的代码时，说：

书上的代码有几个缺点:

 1.算法加入侵入式（intrusive）的资料nMaxLeft,nMaxRight

 2.使用全局变量nMaxLen。

每次使用要额外初始化。

而且就算是不同的独立资料，也不能在多个线程使用这个函数

 3.逻辑比较复杂，也有许多NULL相关的条件测试。

于是给出了下述改进代码：

1.RESULT GetMaximumDistance（NODE* root）  

2.{  

3.  if （!

root）  

4.  {  

5.    RESULT empty = { 0, -1 };    

6.    // trick:

 nMaxDepth is -1 and then caller will plus 1 to balance it as zero.  

7.    return empty;  

8.  }  

9.          

10.  RESULT lhs = GetMaximumDistance（root->pLeft）;    

11.  RESULT rhs = GetMaximumDistance（root->pRight）;  

12.          

13.  RESULT result;  

14.  

15.  //nMaxDepth 就是左子树或右子树的深度加1；  

16.  result.nMaxDepth = max（lhs.nMaxDepth + 1, rhs.nMaxDepth + 1）;   

17.  

18.  //nMaxDistance 则取A和B情况的最大值。

19.  result.nMaxDistance =   

20.    max（max（lhs.nMaxDistance, rhs.nMaxDistance）, lhs.nMaxDepth + rhs.nMaxDepth + 2）;  

21.    //B：

不通过根节点时，取左右子树中最大距离的大值，A：

通过根节点，左+右+2.  

22.   

23.  return result;  

24.}  

第12题（语法）

题目：

求1+2+…+n，

要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?

B:

C）。

    Sorehead：

说实话，我比较反感这种题目，这不是什么算法，就是一些纯技巧方面的东西，有点像我们很多考试的题目，根本就不能代表什么。

   刚看到这个题目，我的第一想法就是多半只能用递规解决，接下来难点就是递规如何结束。

题目的要求是比较苛刻的，楼主答案里面用的两种方法确实挺巧妙的，但我不会C++，因此只能另外想办法。

下面是我写的代码：

intsum（intn）

{

       intval=0;

       n>0&&（val=n+sum（n-1））;

       returnval;

}

虽然功能是实现了，但这个代码编译时是有警告的，当然这个警告不重要。

但我总觉得有更加合适的方法。

或者如leeyunce所说：

思路：

模板元编程，最快捷的计算方式，编译期完成计算

#include

usingnamespacestd;

template

structCalCls

{

   enum{sum=CalCls:

:

sum+N};

};

template<>

structCalCls<0>

{    

   enum{sum=0};

};

intmain（）

{

   cout<<"1+2+3+...+100="<:

:

sum<

   return0;

}

另，一位兄台，短短三行代码想解决第12题，是否正确列?

：

intsum（intn）

{

   return（（n*（n+1））>>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;

       while（p!

=NULL）

       {

               p=p->next;

               q=q->next;

       }

       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

输出：