二叉树类型笔试面试题大总结（含代码）

一、二叉树的遍历-前序、中序、后序以及层次遍历（递归与非递归）

参考另外一篇笔记《二叉树的遍历-递归与非递归 -海子 - 博客园》。

二、重建二叉树，依据前序遍历结果和中序遍历结果

《剑指Offer》面试题6.

思想：递归

代码：

// 《剑指Offer——名企面试官精讲典型编程题》代码

// 著作权所有者：何海涛

struct BinaryTreeNode

{

intm_nValue;

BinaryTreeNode*m_pLeft;

BinaryTreeNode*m_pRight;

};

BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder);

BinaryTreeNode* Construct(int* preorder,int* inorder,int length)

{

if(preorder== NULL|| inorder == NULL|| length<=0)

return NULL;

returnConstructCore(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;

}

// ====================测试代码====================

void Test(char* testName,int* preorder,int* inorder,int length)

{

if(testName!= NULL)

printf("%s begins:\n",testName);

printf("The preorder sequence is: ");

for(int i=0; i< length; ++ i)

printf("%d ",preorder[i]);

printf("\n");

printf("The inorder sequence is: ");

for(int i=0; i< length; ++ i)

printf("%d ",inorder[i]);

printf("\n");

try

{

BinaryTreeNode* root= Construct(preorder,inorder, length);

PrintTree(root);

DestroyTree(root);

}

catch(std::exception& exception)

{

printf("Invalid Input.\n");

}

}

三、判断二叉搜索树的后序遍历是否合法

思想：通过根节点将序列划分为左子树序列和右子树序列，他们必须满足的条件是：左子树序列中的所有值小于根节点，右子树中所有值大于根节点，然后递归判断左子树序列和右子树序列。

代码：

// BST：BinarySearch Tree，二叉搜索树

boolVerifySquenceOfBST(intsequence[],intlength )

{

if (sequence==NULL||length<=0)

returnfalse ;

introot=sequence[ length-1];

//在二叉搜索树中左子树的结点小于根结点

inti=0;

for(;i<length-1;++i )

{

if ( sequence [ i ]>root )

break ;

}

//在二叉搜索树中右子树的结点大于根结点

intj=i ;

for(;j<length-1;++j )

{

if ( sequence [ j ]<root )

returnfalse ;

}

//判断左子树是不是二叉搜索树

boolleft=true ;

if ( i>0)

left=VerifySquenceOfBST( sequence ,i );

//判断右子树是不是二叉搜索树

boolright=true ;

if ( i<length-1)

right=VerifySquenceOfBST( sequence+i ,length-i-1);

return(left&&right ); }

四、二叉树中和为某一值的路径

《剑指Offer》面试题25

同样是递归思想。

代码：

void find_path(BinaryTreeNode *root,intexpected_sun){

vector<int>path;

intcur_sum =0;

find_path(root,expected_sun,path,cur_sum);

}

void find_path(BinaryTreeNode *root,intexpected_sun,vector<int>&path,int cur_sum){

cur_sum +=root->m_nValue;

path.push_back(root->m_nValue);

// 当前节点是叶子节点而且路径上节点值的和满足条件

if(expected_sun == cur_sum && NULL ==root->m_pLeft &&NULL == root->m_pRight)

{

//输出路径

vector<int>::iterator iter=path.begin();

cout << "Path:";

for(;iter != path.end();++iter)

{

cout<< *iter<< "";

}

cout << endl;

}

if(root->m_pLeft!=NULL)

{

find_path(root->m_pLeft,expected_sun,path,cur_sum);

}

if(root->m_pRight!=NULL)

{

find_path(root->m_pRight,expected_sun,path,cur_sum);

}

path.pop_back();

cur_sum -=root->m_nValue;

}

五、将二叉搜索树转化为双向链表

思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

代码：

/////////////////////////////////////////////////////////////////////

//

Covert a sub binary - search- tree into a sorteddouble- linked list

//Input: pNode - the head of the sub tree

//asRight - whether pNode is the right child of its parent

//Output: if asRight is true, return the least node in the sub-tree

//else return the greatest node in the sub-tree

/////////////////////////////////////////////////////////////////////

//

BSTreeNode * ConvertNode(BSTreeNode* pNode,bool asRight)

{

if (! pNode)

return NULL;

BSTreeNode * pLeft= NULL;

BSTreeNode * pRight= NULL;

// Convert the left sub-tree

if (pNode-> m_pLeft)

pLeft=ConvertNode(pNode-> m_pLeft,false );

//Connectthegreatestnodeintheleftsub-treetothecurrentnode

if (pLeft)

{

pLeft-> m_pRight= pNode;

pNode-> m_pLeft= pLeft;

}

// Convert the right sub-tree

if (pNode-> m_pRight)

pRight=ConvertNode(pNode-> m_pRight,true );

//Connecttheleastnodeintherightsub-treetothe currentnode

if (pRight)

{

pNode-> m_pRight= pRight;

pRight-> m_pLeft= pNode;

}

BSTreeNode * pTemp= pNode;

// If the current node is the right child ofits parent,

//returnthe leastnodeinthetreewhoserootisthecurrent node

if (asRight)

{

while (pTemp-> m_pLeft)

pTemp= pTemp-> m_pLeft;

}

// If the current node is the left child ofits parent,

//returnthegreatestnodeinthetreewhoserootisthecurrentnode

else

{

while (pTemp-> m_pRight)

pTemp= pTemp-> m_pRight;

}

return pTemp;

}

/////////////////////////////////////////////////////////////////////

//

Covert a binary search tree into a sorted double- linked list

//Input: the head of tree

//Output: the head of sorted double-linked list

/////////////////////////////////////////////////////////////////////

//

BSTreeNode * Convert(BSTreeNode* pHeadOfTree)

{

// As wewant to return the headof the sorteddouble-linked list,

// we set the second parameter to be true

returnConvertNode(pHeadOfTree,true );

}

思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

代码：

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)

{

BinaryTreeNode *pLastNodeInList = NULL;

ConvertNode(pRootOfTree,&pLastNodeInList);

//pLastNodeInList指向双向链表的尾结点，

//我们需要返回头结点

BinaryTreeNode *pHeadOfList = pLastNodeInList;

while(pHeadOfList!= NULL&& pHeadOfList->m_pLeft!= NULL)

pHeadOfList= pHeadOfList->m_pLeft;

return pHeadOfList;

}

voidConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)

{

if(pNode== NULL)

return;

BinaryTreeNode *pCurrent = pNode;

if (pCurrent->m_pLeft!= NULL)

ConvertNode(pCurrent->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);

}

六、求二叉树的深度

剑指Offer面试题39.

递归：

intTreeDepth(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);

}

七、判断一棵二叉树是否是平衡二叉树

解法一（常规解法）：

分别求左右子树的深度，再进行判断。递归。

此方法会遍历一个节点多次，效率不高。

boolIsBalanced_Solution1 (BinaryTreeNode *pRoot )

{

if ( pRoot==NULL )

returntrue ;

intleft=TreeDepth ( pRoot->m_pLeft );

intright=TreeDepth ( pRoot->m_pRight );

intdiff=left-right ;

if ( diff>1||diff<-1 )

returnfalse ;

returnIsBalanced_Solution1 ( pRoot - >m_pLeft )

&&IsBalanced_Solution1 ( pRoot - >m_pRight );

}

解法二（更高效的解法）：

解决了遍历一个问题多次的问题。用后序遍历的方式遍历二叉树的每一个节点，在遍历到一个节点之前我们就已经遍历了它的左右子树。只要在遍历每个节点的时候记录深度，就可以一边遍历一边判断每个节点是不是平衡的。

bool IsBalanced_Solution2(BinaryTreeNode * pRoot)

{

int depth =0 ;

return IsBalanced(pRoot,& depth);

}

bool IsBalanced(BinaryTreeNode * pRoot, int* pDepth)

{

if (pRoot == NULL)

{

* pDepth=0 ;

return true ;

}

intleft, right;

if (IsBalanced(pRoot-> m_pLeft,& left)

&& IsBalanced(pRoot-> m_pRight,& right))

{

int diff = left - right;

if (diff <=1&& diff>=-1 )

{

* pDepth=1+ (left> right ? left : right);

return true ;

}

}

returnfalse ;

}

八、求二叉树第K层节点个数

递归解法：

（1）如果二叉树为空或者k<1返回0

（2）如果二叉树不为空并且k==1，返回1

（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

参考代码如下：

intGetNodeNumKthLevel(BinaryTreeNode* pRoot,int k)

{

if(pRoot== NULL|| k <1)

return0;

if(k==1)

return1;

int numLeft=GetNodeNumKthLevel(pRoot->m_pLeft, k-1); //左子树中k-1层的节点个数

int numRight=GetNodeNumKthLevel(pRoot->m_pRight, k-1); //右子树中k-1层的节点个数

return (numLeft+ numRight);

}

九、求二叉树中两个节点的最低公共祖先节点

参考另外一篇笔记。

十、求二叉树中两个节点的最大距离

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

递归解法：

（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0

（2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。

参考代码如下：

intGetMaxDistance(BinaryTreeNode* pRoot,int& maxLeft,int& maxRight)

{

//maxLeft, 左子树中的节点距离根节点的最远距离

//maxRight, 右子树中的节点距离根节点的最远距离

if(pRoot== NULL)

{

maxLeft =0;

maxRight =0;

return0;

}

int maxLL, maxLR, maxRL, maxRR;

int maxDistLeft, maxDistRight;

if(pRoot->m_pLeft!= NULL)

{

maxDistLeft=GetMaxDistance(pRoot->m_pLeft, maxLL, maxLR);

maxLeft = max(maxLL, maxLR)+1;

}

else

{

maxDistLeft=0;

maxLeft =0;

}

if(pRoot->m_pRight!= NULL)

{

maxDistRight=GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);

maxRight = max(maxRL, maxRR)+1;

}

else

{

maxDistRight=0;

maxRight =0;

}

return max(max(maxDistLeft,maxDistRight), maxLeft+maxRight);

}

十一、判断一棵二叉树是否为完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。

boolIsCompleteBinaryTree(BinaryTreeNode* pRoot)

{

if(pRoot== NULL)

returnfalse;

queue<BinaryTreeNode*> q;

q.push(pRoot);

bool mustHaveNoChild=false;

bool result=true;

while(!q.empty())

{

BinaryTreeNode* pNode= q.front();

q.pop();

if(mustHaveNoChild) //已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空）

{

if(pNode->m_pLeft!= NULL || pNode->m_pRight!= NULL)

{

result=false;

break;

}

}

else

{

if(pNode->m_pLeft!= NULL && pNode->m_pRight!= NULL)

{

q.push(pNode->m_pLeft);

q.push(pNode->m_pRight);

}

elseif(pNode->m_pLeft!= NULL && pNode->m_pRight== NULL)

{

mustHaveNoChild=true;

q.push(pNode->m_pLeft);

}

elseif(pNode->m_pLeft== NULL && pNode->m_pRight!= NULL)

{

result=false;

break;

}

else

{

mustHaveNoChild=true;

}

}

}

return result;

}

参考资料：

http://blog.csdn.net/luckyxiaoqiang/article/details/7518888