`

程序员面试题精选(11)-求二元查找树的镜像

阅读更多

题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入:
      8
     /   \
   6       10
/\        /\
5   7     9    11
输出:
       8
     /   \
   10     6
/\       /\
11   9   7   5
定义二元查找树的结点为:

C++代码 复制代码
  1. struct BSTreeNode // a node in the binary search tree (BST)   
  2. {   
  3.       int           m_nValue; // value of node   
  4.        BSTreeNode   *m_pLeft;  // left child of node   
  5.        BSTreeNode   *m_pRight; // right child of node   
  6. };  
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
};


分析:尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感觉,就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8,我们交换它的左右子树得到:
       8
     /   \
   10     6
/\       /\
9   11   5   7
我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到:
       8
     /   \
   10     6
/\       /\
11   9 7    5
刚好就是要求的输出。
上面的分析印证了我们的直觉:在遍历二元查找树时每访问到一个结点,交换它的左右子树。这种思路用递归不难实现,将遍历二元查找树的代码稍作修改就可以了。参考代码如下:

C++代码 复制代码
  1. ///////////////////////////////////////////////////////////////////////   
  2. // Mirror a BST (swap the left right child of each node) recursively   
  3. // the head of BST in initial call   
  4. ///////////////////////////////////////////////////////////////////////   
  5. void MirrorRecursively(BSTreeNode *pNode)   
  6. {   
  7.       if(!pNode)   
  8.             return;   
  9.   
  10.       // swap the right and left child sub-tree   
  11.        BSTreeNode *pTemp = pNode->m_pLeft;   
  12.        pNode->m_pLeft = pNode->m_pRight;   
  13.        pNode->m_pRight = pTemp;   
  14.   
  15.       // mirror left child sub-tree if not null   
  16.       if(pNode->m_pLeft)   
  17.              MirrorRecursively(pNode->m_pLeft);     
  18.   
  19.       // mirror right child sub-tree if not null   
  20.       if(pNode->m_pRight)   
  21.              MirrorRecursively(pNode->m_pRight);    
  22. }  
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) recursively
// the head of BST in initial call
///////////////////////////////////////////////////////////////////////
void MirrorRecursively(BSTreeNode *pNode)
{
      if(!pNode)
            return;

      // swap the right and left child sub-tree
       BSTreeNode *pTemp = pNode->m_pLeft;
       pNode->m_pLeft = pNode->m_pRight;
       pNode->m_pRight = pTemp;

      // mirror left child sub-tree if not null
      if(pNode->m_pLeft)
             MirrorRecursively(pNode->m_pLeft);  

      // mirror right child sub-tree if not null
      if(pNode->m_pRight)
             MirrorRecursively(pNode->m_pRight); 
}

由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:

C++代码 复制代码
  1. ///////////////////////////////////////////////////////////////////////   
  2. // Mirror a BST (swap the left right child of each node) Iteratively   
  3. // Input: pTreeHead: the head of BST   
  4. ///////////////////////////////////////////////////////////////////////   
  5. void MirrorIteratively(BSTreeNode *pTreeHead)   
  6. {   
  7.       if(!pTreeHead)   
  8.             return;   
  9.   
  10.       std::stack<BSTreeNode *> stackTreeNode;   
  11.        stackTreeNode.push(pTreeHead);   
  12.   
  13.       while(stackTreeNode.size())   
  14.        {   
  15.              BSTreeNode *pNode = stackTreeNode.top();   
  16.              stackTreeNode.pop();   
  17.   
  18.             // swap the right and left child sub-tree   
  19.              BSTreeNode *pTemp = pNode->m_pLeft;   
  20.              pNode->m_pLeft = pNode->m_pRight;   
  21.              pNode->m_pRight = pTemp;   
  22.   
  23.             // push left child sub-tree into stack if not null   
  24.             if(pNode->m_pLeft)   
  25.                    stackTreeNode.push(pNode->m_pLeft);   
  26.   
  27.             // push right child sub-tree into stack if not null   
  28.             if(pNode->m_pRight)   
  29.                    stackTreeNode.push(pNode->m_pRight);   
  30.        }   
  31. }  
分享到:
评论

相关推荐

    程序员面试题精选100题-何海涛

    《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...

    程序员面试题精选100题

    程序员面试题精选100题 本资源是程序员面试题精选100题,涵盖了算法、数据结构、操作系统、计算机网络、数据库等多个领域。今天,我们将深入分析其中的一道题目,即将二元查找树转换成排序的双向链表。 知识点一:...

    java程序员面试题150例-java常见面试题-java工程师面试题-java面试题大全

    java程序员面试题150例 java常见面试题 java工程师面试题 java面试题大全 带搜索功能,能非常方便的查找到你想要了解的 java面试题目 推荐大家下载。

    程序员面试题精选100题(经典!)

    具体来说,文档中详细讨论了一个在程序员面试中常见的算法问题:如何将二元查找树(Binary Search Tree,BST)转换为一个排序的双向链表。这是一个涉及树的遍历、指针操作、递归思维的经典算法问题。下面将详细介绍...

    程序员面试题精选100题.docx

    本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...

    程序员面试题精选(1-57)

    本资源"程序员面试题精选(1-57)"显然是一个汇集了众多面试题目的集合,涵盖了从基础到高级的各种问题,旨在帮助求职者提升自己的技能并顺利通过面试。 首先,我们要理解数据结构的重要性。数据结构是组织和存储数据...

    程序员考试试题---程序员考试教程

    【程序员考试试题---程序员考试教程】是一系列针对程序员资格认证的考试资料,这些文档主要包含历年的考试试题,旨在帮助备考者熟悉考试形式,提升编程技能和理论知识。程序员考试通常涵盖计算机科学基础,编程语言...

    程序员面试宝典 第5版-欧立奇.part2.rar

    程序员面试宝典 第5版-欧立奇.part2.rar

    程序员面试题精选 C++ 算法 微软 google

    程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google

    java程序员早期面试题汇总.zip

    ------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------

    程序员面试题精选100题【数据结构 /算法】

    - **二元查找树转双向链表:** 这是一道典型的二叉树操作题目,要求不创建新节点,只调整树中节点的指针,将其转换为排序的双向链表。两种常见的解题思路是: - **递归法1:** 从根节点开始,先处理左子树,将左...

    人事面试题150问-人事面试题大全-net程序员面试题--软件开发工程师面试题.xls

    人事面试题150问完整版,附加.NET程序员面试题,所有题目绝对真实有效,欢迎下载!O(∩_∩)O哈哈~

    程序员面试题精选63题

    在程序员面试中,数据结构和算法是经常被考察的重要领域,尤其是涉及到二元查找树(Binary Search Tree, BST)的问题。本题目的核心是将一个二元查找树转换成一个排序的双向链表,这涉及到对树结构的深入理解和递归...

    程序员面试题精选100题(自己整理)

    1. **二元查找树(Binary Search Tree, BST)** 二元查找树是一种特殊的二叉树,其中每个节点的值都大于其左子树中任何节点的值,小于其右子树中任何节点的值。这种特性使得在二元查找树中进行查找、插入和删除操作...

    程序员面试题精选100题完整版

    本题要求将二叉查找树转化为一个排序的双向链表,这一转换不仅考验应聘者对二叉树特性的理解,同时也考察了其对链表操作的熟练程度。 #### 1.2 题目描述 题目要求输入一棵二叉查找树,并将其转换为一个排序的双向...

Global site tag (gtag.js) - Google Analytics