一、二叉树的遍历-前序、中序、后序以及层次遍历(递归与非递归)参考另外一篇笔记《二叉树的遍历-递归与非递归 -海子 - 博客园》。
二、重建二叉树,依据前序遍历结果和中序遍历结果《剑指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; 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,二叉搜索树 bool VerifySquenceOfBST(int sequence[], int length ) { if (sequence == NULL || length <=0) return false ; 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 ) return false ; } //判断左子树是不是二叉搜索树 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 ); }
四、二叉树中和为某一值的路径《剑指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); }
七、判断一棵二叉树是否是平衡二叉树解法一(常规解法): 分别求左右子树的深度,再进行判断。递归。 此方法会遍历一个节点多次,效率不高。 bool IsBalanced_Solution1 (BinaryTreeNode * pRoot ) { if ( pRoot == NULL ) return true ; int left = TreeDepth ( pRoot->m_pLeft ); int right = TreeDepth ( pRoot->m_pRight ); int diff = left - right ; if ( diff >1|| diff <-1 ) return false ; return IsBalanced_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; }
参考资料: |
|