參考另外一篇筆記《二叉樹的遍歷-遞歸與非遞歸 -海子 - 博客園》。
《劍指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 ;
}
遞歸解法：
（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
新聞熱點
疑難解答
