1、判斷二叉樹是否為完全二叉樹：

層序遍歷，從上到下，從左到右，遍歷二叉樹；

當遇到一個節點的左子樹為空時，則該節點的右子樹為空和后面遍歷的節點都為葉子節點，否則不是完全二叉樹。

當該節點只有左子樹時，且該子樹為葉子結點，否則不為完全二叉樹。

判斷實現：

bool _IsCompleteBinaryTree(BinaryTreeNode<T>* pRoot){if(pRoot == NULL)return false;queue<BinaryTreeNode<T>*> q;q.push(pRoot);bool IsOnlyLeft = false;bool ret = true;while(!q.empty()){BinaryTreeNode<T>* pNode = q.front();q.pop();if(IsOnlyLeft)//找到了只有左子樹的節點{if(pNode->_Left != NULL || pNode->_Right != NULL){ret = false;//不是完全二叉樹break;}}else{if(pNode->_Left != NULL && pNode->_Right != NULL){q.push(pNode->_Left);q.push(pNode->_Right);}else if(pNode->_Left != NULL && pNode->_Right == NULL){IsOnlyLeft = true; //找到只有左子樹的節點q.push(pNode->_Left);}else if(pNode->_Left == NULL && pNode->_Right != NULL){ret = false;break;}else{IsOnlyLeft = true;}}}return ret;}
2、求二叉樹的鏡像

遞歸：

void _Mirror(BinaryTreeNode<T>*& pRoot){if(pRoot == NULL)return;BinaryTreeNode<T>* Left = _Mirror(pRoot->_Left);BinaryTreeNode<T>* Right = _Mirror(pRoot->_Right);pRoot->_Left = Right;pRoot->_Right = Left;}
非遞歸：循環（棧）

void _Mirror_nor(BinaryTreeNode<T>*& pRoot) { if(NULL == pRoot) return; stack<BinaryTreeNode<T>*> stackTreeNode; stackTreeNode.push(pRoot); while(stackTreeNode.size()) { BinaryTreeNode<T>* pNode = stackTreeNode.top(); stackTreeNode.pop(); if(NULL != pNode->Left || NULL != pNode->Right) { BinaryTreeNode<T>* pTemp = pNode->Left; pNode->Left = pNode->Right; pNode->Right = pTemp; } if(NULL != pNode->Left) stackTreeNode.push(pNode->Left); if(NULL != pNode->Right) stackTreeNode.push(pNode->Right); } }

總結

以上是生活随笔為你收集整理的二叉树面试题：判断树是否为完全二叉树和求二叉树的镜像的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。