面试常备题---二叉树总结篇（zt)

     人生就像是一场长跑，有很多机会，但也得看我们是否能够及时抓牢，就像下面这样的代码：

while(isRunning)
{
     if(...){...}
     else if(...){...}
     ...
     else{..}
}

      存在着太多的if...else if...else...，很多都是一闪而过，就看我们是否将isRunning时刻设置为true，一直不断在跑，一直不断在检查条件是否满足。就算条件达到了，有些人会选择return或者将isRunning设置为false，主动退出循环，有些人选择继续跑下去，不断追寻更高的目标。
      所以，如果我们一时看不到未来，请不断跑下去，迟早会有某个条件满足的，只要设置的条件是合理可达的。

      在实际编程中，树是经常遇到的数据结构，但可惜的是，我们经常不知道该用树了。实际情况就是，我们在避免过早使用数据结构，以防止引入不必要的复杂性。

      树的逻辑非常简单：除了根结点外，其他每个结点都只有一个父结点，除了叶结点外，其他所有结点都有一个或多个子结点。父结点和子结点间用指针链接。树有很多种形式，最常见的是二叉树，每个结点最多只有两个子结点。

      二叉树中最重要的操作就是遍历，通常有中序遍历，前序遍历和后序遍历，简单一点讲，这三种遍历的区别就是根结点的遍历顺序问题，像是中序遍历就是左，根，右，而前序遍历是根，左，右，后序遍历则是左，右，根。复杂一点的遍历就是宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点...一直到最下面一层结点。在同一层结点中，从左到右的顺序依次访问。

     常见的二叉树结点的定义如下：

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

      二叉树中还有许多形式，像是二叉搜索树，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。另外两种常见的形式就是堆和红黑树。堆分为最大堆和最小堆，在最大堆中，根结点的值最大，最小堆则相反。堆非常适合用于快速查找最值，像是堆排序，就是利用了这点。红黑树是把树中的结点定义为红和黑两种颜色，并通过规则确保从根结点到叶结点的最长路径的长度不超过最短路径的两倍。很多C++的STL都是基于红黑树实现的，像是set,multiset,map,multimap等数据结构。

题目一：输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树。

     在拿到这道题目的时候，我们首先明确一点，就是如何根据前序遍历和中序遍历来求出根结点。根结点对于二叉树来说，至关重要，只有先确定根结点，我们才能确定其他结点。

     我们还是从一个测试用例开始。

     假设某个二叉树的前序遍历结果为{1, 2, 4, 7, 3, 5, 6, 8}, 中序遍历的结果为{4, 7, 2, 1, 5, 3, 8, 6}。因为二叉树的前序遍历是根据：根，左，右的顺序来，所以前序遍历开头的元素就是根结点，也就是说，1就是二叉树的根结点。然后再看看中序遍历：左， 根，右，前面已经确定了1就是根结点，那么1的左边序列就是二叉树左边的元素，也就是说，{4， 7， 2}就是二叉树左边的元素，而{5， 3， 8， 6}就是二叉树右边的元素。

     二叉树的特点就是任何非叶结点的结点都可以成为根结点，所以我们可以从上面得到的两个序列中，按照之前的分析推敲出整个树的结构，也就是采用递归的方法。

BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
     if(preorder == NULL || inorder == NULL || length <= 0)
     {
           return NULL;
     }

     return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}

BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
{
     int rootValue = startPreorder[0];
     BinaryTreeNode* root = new BinaryTreeNode();
     root->m_nValue = rootValue;
     root->m_pLeft = root->m_pRight = NULL;

     if(startPreorder == endPreorder)
    {
          if(startInorder == endInorder && *startPreorder == *startInorder)
          {
                return root;
          }
          else
          {
                throw std :: exception("Invalid input.");
           }
    }

    int* rootInorder = startInorder;
    while(rootInorder <= endInorder && *rootInorder != rootValue)
    {
        ++rootInorder;
    }

    if(rootInorder == endInorder && *rootInorder != rootValue)
    {
         throw std :: exception("Invalid input.");
    }

    int leftLength = rootInorder - startInorder;
    int* leftPreorderEnd = startPreorder + leftLength;
    if(leftLength > 0)
    {
         root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
    }
    if(leftLength < endPreorder - startPreorder)
   {
         root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
   }

   return root;
}

题目二：输入两棵二叉树A和B，判断B是不是A的子结构。

     要确定B是不是A的子结构，我们可以先在A中找到B的根结点，然后再看看这个根结点下面的左右结点是否和B相同。也就是说，我们首先要遍历二叉树A。

     二叉树特别适合使用递归的方式，这道题也不例外：

bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
     if(pRoot2 == NULL)
    {
         return true;
    }

    if(pRoot1 == NULL)
    {
         return false;
    }

    if(pRoot1->m_nVlaue != pRoot2->m_nValue)
   {
         return false;
   }

   return DoesTree1HaveTree2(pRoot->m_pLeft, pRoot2->m_pLeft) && DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}

     解决二叉树的编程问题，需要注意的有两方面：鲁棒性和简洁性。因为二叉树涉及到大量的指针操作，所以每次使用指针的时候我们都必须提醒自己：是否有空指针的危险。

     简洁性对于二叉树问题求解非常重要，因为大量的指针操作非常容易出现问题，就算我们已经足够小心了，但最好就是通过使用递归来让代码更加简洁，这样就可以少写几个指针，少犯点错误。

题目三：输入一个二叉树，输出它的镜像。

     所谓的二叉树镜像，其实也就是将一个结点的左右子结点交换，就像我们平时照镜子一样。

     根据这样的原理，我们知道，这是一个前序遍历二叉树，然后在找到左右子结点后将它们进行交换的过程。

void MirrorRecursively(BinaryTreeNode* pNode)
{
     if(pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight))
    {
         return;
    }

    BinaryTreeNode* pTemp = pNode->m_pLeft;
    pNode->m_pLeft = pNode->m_pRight;
    pNode->m_pRight = pTemp;

    if(pNode->m_pLeft)
    {
          MirrorRecursively(pNode->m_pLeft);
    }

   if(pNode->m_pRight)
   {
         MirrorRecursively(pNode->m_pRight);
   }
}

题目四：从上到下打印二叉树的每个结点，同一层的结点按照从左到右的顺序。

     要想在一开始就想好这个过程可不太容易，我们还是得先从一个测试用例开始。

     假设这树的结构如下：

                              8

                       6           10

                  5        7    9     11

     那么我们先是打印出8，然后将它的子结点6和10保存起来，然后打印6，保存它的两个子结点5和7，接着打印10...到了这里，可以察觉到，比起5和7,10先存放起来，然后又先打印出来，说明这是一个"先进先出"的结构，也就是所谓的队列。

     这就是宽度优先遍历，代码如下：

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)
{
     if(!pTreeRoot)
     {
         return;
     }

     std :: deque<BinaryTreeNode*> dequeTreeNode;

     dequeTreeNode.push_back(pTreeRoot);

     while(dequeTreeNode.size())
     {
          BinaryTreeNode* pNode = dequeTreeNode.front();
          dequeTreeNode.pop_front();

          printf("%d ", pNode->m_nValue);
   
          if(pNode->m_pLeft)
          {
               dequeTreeNode.push_back(pNode->m_pLeft);
          }

          if(pNode->m_pRight)
          {
               dequeTreeNode.push_back(pNode->m_pRight);
          }
     }
}

     分析数据的存储和访问，我们就可以决定应该用什么样的数据结构来完成任务。

     大部分有关树的遍历问题其实都是考察我们是否对树的结构和遍历算法足够了解，能否利用递归写出正确的代码。

题目五：输入一个整数数组，判断该数组是否是某二叉搜索树的后序遍历的结果。

     这种题目是最常见的，就算是后序遍历这种常见的遍历算法，要想完全写好代码还是不容易的：  

bool VerifySquenceOfBST(int sequence[], int length)
{
     if(sequence == NULL || length <= 0)
     {
           return false;
     }

     int root = sequence[length - 1];
     
     int i = 0;
     for(; i < length; ++i)
     {
          if(sequence[i] > root)
          {
                break;
          }
     }

     int j = i;
     for(; j < length; ++j)
    {
         if(sequence[j] < root)
         {
               return false;
         }
    }

    bool left = true;
    if(i > 0)
    {
         left = VerifySequenceOfBST(sequence, i);
    }

    bool right = true;
    if(i < length - 1)
    {
         right = VerifySequenceOfBST(sequence + i, length - i - 1);
    }

    return left && right;
}

     结合二叉搜索树的特点，再加上递归，这个代码不难实现。
     利用二叉树的遍历算法，我们能够做很多事情，像是这道题目：

题目六：输入一棵二叉树和某个整数值，打印出二叉树中结点值的和为输入整数的所有路径，所谓的路径，是指从根结点开始到叶结点，形成一条路径。

     在二叉树的所有遍历算法中，只有前序遍历是从根结点开始的，所以我们可以考虑一下前序遍历。既然是要计算路径上所有值的总和，那么保存路径上的每个值也是必要的。更重要的步骤是当我们发现这条路径不对时，要能够返回到叶结点的根结点，并且删除掉这些值，也就是说，路径上的值是"先进后出"，也就是栈的结构。

void FindPath(BinaryTreeNode* pRoot, int expectedSum)
{
      if(pRoot == NULL)
      {
           return;
      }

      std :: vector<int> path;
      int currentSum = 0;
      FindPath(pRoot, expectedSum, path, currentSum);
}

void FindPath(BinaryTreeNode* pRoot, int expectedSum., std :: vector<int>& path, int& currentSum)
{
     currentSum += pRoot->m_nValue;
     path.push_back(pRoot->m_nValue);
     
     bool isLeft = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
     if(currentSum == expectedSum && isLeft)
     {
           printf("A path is found: ");
           std :: Vector<int> :: iterator iter = path.begin();
           for(; iter != path.end(); ++iter)
           {
                printf("%d	", *iter);
           }
      printf("
");
     }

    if(pRoot->m_pLeft != NULL)
    {
           FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
    }
    if(pRoot->m_pRight != NULL)
    {
          FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
    }

    currentSum -= pRoot->m_nValue;
    path.pop_back();
}

     上面的代码只要仔细看一下，就会发现很严谨，像是我们在传递一个容器色时候，一般都是传递它的引用，这是为了防止传参的时候的副本复制，但是引用的作用并不仅仅如此，像是接下来的参数currentSum之所以是int&，是因为我们希望该值能够在函数递归调用的时候被改变，如果不是这样，离开该函数后，currentSum就会变为原值，因为它只是原本的currentSum的一个副本。
      这里我们并不使用STL中的stack，而是采用vector的原因就是stack只能取得栈顶的元素。

      树和链表之间还可以相互转化，这也可以成为一个考点：

题目七：输入一棵二叉树，将该树转化成一个排序的双向链表，要求不能创建任何新的结点，只能调整树中结点指针的指向。

      二叉树中的左结点总是比根结点小，而右结点又比根结点大，在双向链表中，每个结点都有两个指针，一个指向前面的结点，另一个指向后面的结点。根据这样的特性，二叉树的确可以转换成排序的双向链表。

      由于需要排序，在二叉树所有遍历算法中，只有中序遍历是按照顺序来的。 

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
     BinaryTreeNode* pLastNodeInList = NULL;
     ConvertNode(pRootOfTree, &pLastNodeInList);

     BinaryTreeNode* pHeadOfList = pLastNodeInList;
     while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
     {
          pHeadOfList = pHeadOfList->m_pLeft;
     }

     return pHeadOfList;
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
     if(pNode == NULL)
     {
          return;
     }

     BinaryTreeNode* pCurrent = pNode;

     if(pCurrent->m_pLeft != NULL)
    {
          ConvertNode(pCurrentNode->m_pLeft, pLastNodeInList);
    }
    
    pCurrent->m_pLeft = *pLastNodeInList;
    if(*pLastNodeInList != NULL)
    {
        (*pLastNodeInList)->m_pRight = pCurrent;
    }

    *pLastNodeInList = pCurrent;
    
    if(pCurrent->m_pRight != NULL)
    {
         ConvertNode(pCurrent->m_pRight, pLastNodeInList);
    }
}

      二叉树不仅可以看成链表，也可以看成图。

题目八：如果我们将二叉树看成一个图，父子结点间的连线看成是双向的，将两个结点间的边的个数定义了这两个结点的距离。写一个程序求一棵二叉树中相距最远的两个结点间的距离。

     遇到这种问题，可以自己画几个二叉树来寻找规律：相距最远的两个结点，一定是两个叶结点或者是一个叶结点到它的根结点。

     无论是什么情况，我们都要遍历二叉树中所有结点一次，所以提高效率的关键就是遍历的算法。我们可以采用深度优先遍历算法。

struct Node
{
     Node* pLeft;
     Node* pRight;
     int nMaxKLeft;
     int nMaxRight;
     char cValue;
};

int nMaxLen = 0;

void FindMaxLen(Node* pRoot)
{
     if(pRoot == NULL)
     {
          return;
     }

     if(pRoot->pLeft == NULL)
     {
          pRoot->nMaxLeft = 0;
     }

     if(pRoot->pRight == NULL)
    {
          pRoot->nMaxRight = 0;
    }

    if(pRoot->pLeft != NULL)
    {
          FindMaxLen(pRoot->pLeft);
    }

    if(pRoot->pRight != NULL)
    {
          FindMaxLen(pRoot->pRight);
    }

    if(pRoot->pLeft != NULL)
    {
          int nTempMax = 0;
          if(pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight)
          {
                nTempMax = pRoot->pLeft->nMaxLeft;
          }
          else
          {
                nTempMax = pRoot->pLeft->nMaxRight;
          }

          pRoot->nMaxLeft = nTempMax + 1;
    }

    if(pRoot->pRight != NULL)
    {
          int nTempMax = 0;
          if(pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight)
          {
               nTempMax = pRoot->pRight->nMaxLeft;
          }
           else
          {
               nTempMax = pRoot->pRight->nMaxRight;
          }
          pRoot->nMaxRight = nTempMax + 1;
    }

    if(pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLeft)
   {
          nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
   }
}

     事实上，关于二叉树的讨论，最好的方法就是从画图开始下手，理清楚它的指针是如何移动的，我们就能写出代码了。

     二叉树的深度也是一个重要的考点。

题目九：输入一棵二叉树的根结点，求该树的深度。

     所谓的深度，指的就是从根结点到叶结点依次经过的结点(含根，叶结点)形成树的一条路径，最长路径的长度为树的深度。

     表面上好像需要遍历整棵树，以便知道那部分的结点最多，但实际上根本就不需要这样做。如果一棵树只有一个结点，它的深度为1，如果结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1，同样如果结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1.如果既有左子树又有右子树，那么该树的深度就是其左右子树深度的较大值加1。

     代码如下：

int TreeDepth(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
    {
          return 0;
    }

    int nLeft = TreeDepth(pRoot->m_pLeft);
    int nRight = TreeDepth(pRoot->m_pRight);

    return nLeft > nRight ? nLeft + 1 : nRight + 1;
}

     在这道题的基础上，我们还可以增加难度：
题目十：输入一棵二叉树的根结点，判断该树是否是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

     这不难，我们可以在前面代码的基础上，在每次得到左右子树的深度的时候进行一次判断就可以，但是时间效率不高，和数组遍历一样，从前面开始不行，那么就从后面开始。

     后序遍历的好处就是在我们遍历到一个结点前就已经遍历了它的左右子树，只要在遍历每个结点的时候记录它的深度就可以了。

bool IsBalanced(BinaryTreeNode* pRoot)
{
   int depth = 0;
   return IsBalanced(pRoot, &depth);
}

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
     if(pRoot == NULL)
     {
           *pDepth = 0;
           return true;
     }

     int left, right;
     if(IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right))
     {
           int diff = left - right;
           if(diff <= 1 && diff >= -1)
           {
                 *path = 1 + (left > right ? left : right);
                 return true;
           }
     }

     return false;
}

     上面的题目都是显式的指定二叉树，但实际中的编程可不是这样，像是下面这道：

题目十一：输入n个整数，找出其中最小的k个数。

      第一眼的想法肯定是利用数组来求解。

      我们可以对这些数字进行排序，排序后位于最前面的k个数字就是最小的k个数，这种思路的时间复杂度是O(Nlog2N),前提就是使用快速排序。

      在之前的数组总结中，我们曾经提及过Partition这个函数，这里同样也可以使用：

void GetLeastNumbers(int* input, int n, int* output, int k)
{
      if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
      {
           return;
      }

      int start = 0;
      int end = n - 1;
      int index = Partition(input, n, start, end);
      while(index != k - 1)
      {
           if(index > k - 1)
           {
                  end = index - 1;
                  index = Partition(input, n, start, end);
           }
           else
           {
                   start = index + 1;
                   index = Partition(input, n, start, end);
           }        
       }

        for(int i = 0; i < k; ++i)
        {
              output[i] = input[i];
        }
}

     这种算法的局限就是我们需要修改输入的数组，因为函数Partition会调整数组中数字的顺序。
     我们可以先创建一个大小为k的数据容器来存储最小的k个数字，然后每次从输入的n个整数中读入一个数，如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器中，如果容器中已有k个数字，也就是容器已满，此时我们不能再插入新的数字而只能替换已有的数字。找出已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值还要大，那么这个数字不可能是最小的k个整数之一，于是我们可以抛弃这个整数。

     因此当容器满了之后，我们要做3件事情：一是在k个整数中找到最大数；二是有可能在这个容器中删除最大数；三是有可能要插入一个新的数字。如果用一个二叉树来实现这个容器，那么我们可能在O(log2K)时间内实现这些操作，所以对于n个输入数字而言，总的时间效率就是O(Nlog2K)。

     因为都需要找到k个整数中的最大数字，我们很容易想到用最大堆。在最大堆中，根结点的值总是大于它的子树中的任意结点的值。于是我么每次都可以在O(1)得到已有的k个数字中的最大值，但需要O(log2K)时间完成删除和插入操作。

     自己从头到尾实现一个红黑树是需要一定的代码，我们可以利用现成的基于红黑树的容器：

typedef multiset<int, greater<int>> intSet;
typedef multiset<int, greater<int>> :: iterator setIterator;

void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers, int k)
{
    leastNumbers.clear();
   
    if(k < 1 || data.size() < k)
    {
          return;
     }

     vector<int> :: const_iterator iter = data.begin();
     for(; iter != data.end(); ++iter)
     {
           if((leastNumbers.size()) > k)
           {
                 leastNumbers.insert(*iter);
           }
           else
           {
                 setIterator iterGreatest = leastNumbers.begin();

                 if(*iter < *(leastNumbers.begin())
                 {
                      leastNumbers.erase(iterGreastest);
                      leastNumbers.insert(*iter);
                 }
           }
     }
}

      这种算法的时间复杂度是O(N),比起第一种是慢了，但是它不需要修改原有的数据，而且非常适合海量数据的输入，因为内存大小是有限的，我们根本不可能一次性存入数组中，所以我们只能从辅助空间中每次读入一个数字，再进行判断。