二叉樹面試題-鏡像與判斷是否為完全二叉樹

二叉樹部分面試題

關于二叉樹的一些面試題在下面的文章已經寫過了，

​​點選打開連結​​

在這裡做一些補充。

九、求二叉樹的鏡像

二叉樹的鏡像樹就是把一個節點下的左右孩子交換，例如：

這樣與層序周遊還有些相似，實作如下：

遞歸

//求二叉樹的鏡像
  PNode _MirrorBinTree1(PNode pRoot)
  {
    if (pRoot == NULL)
      return 0;
    swap(pRoot->_left, pRoot->_right);
    _MirrorBinTree1(pRoot->_left);
    _MirrorBinTree1(pRoot->_right);
    return pRoot;
  }      

非遞歸

//求二叉樹的鏡像
  PNode _MirrorBinTree2(PNode pRoot)
  {
    if (pRoot == NULL)
      return 0;
    queue<PNode> q;
    q.push(pRoot);
    while (!q.empty())
    {
      PNode front = q.front();
      swap(front->_left, front->_right);
      q.pop();

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);
    }
  }      

十、判斷二叉樹是否為完全二叉樹

完全二叉樹的概念文章開始已經講過。二叉樹可分為空樹，隻有一個節點，多個節點。而多個節點可分為以下方面：

1、左右子樹均存在

2、隻有左，沒有右

3、隻有右，沒有左（false)

4、沒有左右子樹

我們利用隊列實作，如下：

代碼如下：

bool _CompleteBinTree(PNode pRoot)
  {
    if (pRoot == NULL)
      return 1;
    if (pRoot->_left == NULL && pRoot->_right == NULL)
      return 0;

    queue<PNode> q;
    q.push(pRoot);
    bool flag = false;
    while (!q.empty())
    {
      PNode pCur = q.front();
      q.pop();
      if (pCur->_left == NULL || pCur->_right == NULL)
      {
        if (pCur->_left == NULL&&pCur->_right != NULL)
        {
          q.push(pCur->_left);
          flag = true;
        }
        else if (pCur->_right == NULL&&pCur->_left != NULL)
        {
          flag = false;
        }
        else
          flag = true;
      }
      else
      {
        q.push(pCur->_left);
        q.push(pCur->_right);
      }
    }
    return flag;
  }      

測試：

template<class T>
struct TreeNode
{
  T _data;
  TreeNode *_left;
  TreeNode *_right;
  TreeNode(const T& data)
    :_data(data)
    , _left(NULL)
    , _right(NULL)
  {}
};

template<class T>
class BinTree
{
  typedef TreeNode<T> Node;
  typedef TreeNode<T> *PNode;
public:
  BinTree()
    : _pRoot(NULL)
  {}

  BinTree(const T* array, size_t size, const T& invalid)
  {
    size_t index = 0;
    _pRoot = _CreateBinTree(array, size, index, invalid);
  }

  BinTree(const BinTree& bt)
  {
    _pRoot = _CopyBinTree(bt._pRoot);
  }

  BinTree& operator=(const BinTree& bt)
  {
    if (this == bt)
      return;
    _DestroyBinTree(_pRoot);
    _pRoot = new Node(bt->_data);
    _pRoot->_left = bt->_left;
    _pRoot->_right = bt->_right;
  }

  ~BinTree()
  {
    _DestroyBinTree(_pRoot);
  }

  void PreOrder()
  {
    _PreOrder1(_pRoot);
    cout << endl;
  }

  PNode MirrorBinTree1()
  {

    return _MirrorBinTree1(_pRoot);
  }
  PNode MirrorBinTree2()
  {

    return _MirrorBinTree2(_pRoot);
  }
  bool CompleteBinTree()
  {
    return _CompleteBinTree(_pRoot);
  }      

private:
  //求二叉樹的鏡像
  PNode _MirrorBinTree1(PNode pRoot)
  {
    if (pRoot == NULL)
      return 0;
    swap(pRoot->_left, pRoot->_right);
    _MirrorBinTree1(pRoot->_left);
    _MirrorBinTree1(pRoot->_right);
    return pRoot;
  }
  //求二叉樹的鏡像
  PNode _MirrorBinTree2(PNode pRoot)
  {
    if (pRoot == NULL)
      return 0;
    queue<PNode> q;
    q.push(pRoot);
    while (!q.empty())
    {
      PNode front = q.front();
      swap(front->_left, front->_right);
      q.pop();

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);
    }
  }
  //判斷完全二叉樹
  bool _CompleteBinTree(PNode pRoot)
  {
    if (pRoot == NULL)
      return 1;
    if (pRoot->_left == NULL && pRoot->_right == NULL)
      return 0;

    queue<PNode> q;
    q.push(pRoot);
    bool flag = false;
    while (!q.empty())
    {
      PNode pCur = q.front();
      q.pop();
      if (pCur->_left == NULL || pCur->_right == NULL)
      {
        if (pCur->_left == NULL&&pCur->_right != NULL)
        {
          q.push(pCur->_left);
          flag = true;
        }
        else if (pCur->_right == NULL&&pCur->_left != NULL)
        {
          flag = false;
        }
        else
          flag = true;
      }
      else
      {
        q.push(pCur->_left);
        q.push(pCur->_right);
      }
    }
    return flag;
  }
private:
    PNode _pRoot;
};      

測試：

int main()
{
  //完全二叉樹
  char array1[] = "abc##d##ef##g";
  BinTree<char> bt1(array1,strlen(array1),'#');

  //不完全二叉樹
  char array2[] = "abc###def##g";
  BinTree<char> bt2(array2, strlen(array2), '#');

  bt1.PreOrder();
  bt1.MirrorBinTree1();
  bt1.MirrorBinTree2();
  bt1.PreOrder();

  cout << bt1.CompleteBinTree() << endl;
  cout << bt2.CompleteBinTree() << endl;
  system("pause");
  return 0;
}      

兩次鏡像應該傳回原樣，測試結果：