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

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

参考另外一篇笔记《二叉树的遍历-递归与非递归》 http://www.linuxidc.com/Linux/2014-07/104853.htm。

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

《剑指Offer》面试题6. 思想：递归代码：// 《剑指Offer——名企面试官精讲典型编程题》代码// 著作权所有者：何海涛 struct BinaryTreeNode{int m_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;elsethrow 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: ",testName）; printf（"The preorder sequence is: "）;for（int i=0; i< length; ++ i） printf（"%d ",preorder[i]）; printf（" "）; printf（"The inorder sequence is: "）;for（int i=0; i< length; ++ i） printf（"%d ",inorder[i]）; printf（" "）; try{ BinaryTreeNode* root= Construct（preorder,inorder, length）;PrintTree（root）; DestroyTree（root）;}catch（std::exception& exception）{ printf（"Invalid Input. "）;}}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

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

思想：通过根节点将序列划分为左子树序列和右子树序列，他们必须满足的条件是：左子树序列中的所有值小于根节点，右子树中所有值大于根节点，然后递归判断左子树序列和右子树序列。代码：// BST：BinarySearch Tree，二叉搜索树bool VerifySquenceOfBST（int sequence[], int length ）{if （sequence == NULL || length <=0）returnfalse ;int root = sequence[ length -1]; //在二叉搜索树中左子树的结点小于根结点int i =0;for（; i < length -1;++ i ） {if （ sequence [ i ]> root ）break ; } //在二叉搜索树中右子树的结点大于根结点int j = i ;for（; j < length -1;++ j ） {if （ sequence [ j ]< root ）returnfalse ; } //判断左子树是不是二叉搜索树bool left =true ;if （ i >0） left = VerifySquenceOfBST（ sequence , i ）; //判断右子树是不是二叉搜索树bool right =true ;if （ i < length -1） right = VerifySquenceOfBST（ sequence + i , length - i -1）;return （left && right ）; }更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2014-07/104854p2.htm