【正文】 TreeNode* Convert(TreeNode* pRootOfTree){ if(pRootOfTree==NULL) return NULL。 TreeNode *pre = NULL。 inOrderVisit(pRootOfTree,pre)。 while(preleft!=NULL) pre = preleft。 return pre。 } void inOrderVisit(TreeNode *root, TreeNode *amp。pre){ if(rootleft!=NULL) inOrderVisit(rootleft,pre)。 if(pre!=NULL) preright = root。//當(dāng)前節(jié)點(diǎn)是前驅(qū)節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn) rootleft = pre。//當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) pre = root。 if(rootright!=NULL) inOrderVisit(rootright,pre)。 }}。兩個(gè)代碼的時(shí)間復(fù)雜度是一樣的，不同在于：第一段代碼在遍歷二叉樹過程中，沒有連接正序鏈，而是在返回頭結(jié)點(diǎn)時(shí)才連接；第二段代碼在遍歷二叉樹的過程中就連接了正序鏈。這里需要注意引用或指針的使用，比如下面的代碼是有問題的：class Solution {public: TreeNode* Convert(TreeNode* pRootOfTree){ if(pRootOfTree==NULL) return NULL。 inOrderVisit(pRootOfTree,NULL)。 while(preleft!=NULL) pre = preleft。 return pre。 } void inOrderVisit(TreeNode *root, TreeNode **pre){ if(rootleft!=NULL) inOrderVisit(rootleft,pre)。 if(pre!=NULL)(*pre)right = root。 rootleft = *pre。 *pre = root。 if(rootright!=NULL) inOrderVisit(rootright,pre)。 }}。即使使用了指針pre，但因?yàn)槠錄]有在主函數(shù)中定義，在返回到根節(jié)點(diǎn)時(shí)，其中的值已經(jīng)不存在了，故而會(huì)導(dǎo)致錯(cuò)誤。一定在主函數(shù)中定義pre變量（或者聲明為全局變量）。l 字符串的排列輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。 結(jié)果請按字母順序輸出。字符串長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。代碼：class Solution {public: vectorstring Permutation(string str) { int size = ()。 vectorstring ret。 if(size==0) return ret。 setstring perSet。//使用set來排序和去重 for(int i=0。isize。i++){ swap(str,i,0)。//選出第一個(gè)元素 permutationTmp(str,perSet,1)。//對剩下的size1個(gè)元素全排列 swap(str,i,0)。//復(fù)原字符串 } setstring::iterator iter = ()。 for(。iter!=()。iter++)//將set中元素復(fù)制給vector，用于返回 (*iter)。 return ret。 }//perSet要保存所用排列，所以引用傳遞；而str必須使用值傳遞，不能引用或指針void permutationTmp(string str, setstring amp。perSet, int k){ if(k==()){ (str)。 return。 } for(int i=k。i()。i++){ swap(str,i,k)。 permutationTmp(str,perSet,k+1)。 swap(str,i,k)。 } } void swap(string amp。str, int i, int j){//交換元素 char ch = str[i]。 str[i] = str[j]。 str[j] = ch。 }}。分析：簡單的全排列問題。需要注意的是：字母可能重復(fù)，所以全排列中存在重復(fù)的字符串，要去重。本代碼采用set容器來去重，而且因?yàn)閟et可以自動(dòng)排序，所以也免去了自己去排序的過程。l 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字?jǐn)?shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個(gè)數(shù)字。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。代碼：class Solution {public: int MoreThanHalfNum_Solution(vectorint numbers) { int size = ()。 if(size==0) return 0。 int count = 1。 int num = numbers[0]。 for(int i=1。isize。i++){ if(num!=numbers[i]){ count。 if(count==0){ num = numbers[i]。 count = 1。 } }else{ count++。 } } count = 0。 for(int i=0。isize。i++) if(num==numbers[i]) count++。 if(countsize/2) return num。 else return 0。 }}。分析：時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，很不錯(cuò)的算法。設(shè)定兩個(gè)變量：一個(gè)存放數(shù)字（設(shè)為num），一個(gè)計(jì)數(shù)（設(shè)為count），num初始化為數(shù)組第一個(gè)元素，count初始化為1。從下一個(gè)元素numbers[i]（0isize）開始遍歷數(shù)組，如果num!=numbers[i]，count減一；若count變?yōu)?，則令num=numbers[i]，count=1。如果num==numbers[i]，count加一。那么最后num保存的值就是要找的值（如果存在的話）。 這樣做的理由是：如果存在次數(shù)大于數(shù)組一半的數(shù)，則它出現(xiàn)的次數(shù)比其他所有元素出現(xiàn)次數(shù)之和還要大。 需要注意的是：有可能不存在出現(xiàn)次數(shù)大于數(shù)組一半的數(shù)，所以最后還要判斷num是否滿足出現(xiàn)次數(shù)大于數(shù)組一半。另一種方法是利用快速排序的劃分思想：每次都能確定一個(gè)元素的最終位置，如果這個(gè)位置剛好是size/2+1，那么它就是要找的數(shù)（如果存在的話）。這種算法的時(shí)間復(fù)雜度也是O(n)，但相比于上面的算法，好理解些。如下：代碼（快排思想）：class Solution {public: int MoreThanHalfNum_Solution(vectorint numbers) { int size = ()。 if(size==0) return 0。 int num = partition(numbers)。//找到有序數(shù)組中下標(biāo)為size/2+1的元素 int count = 0。 for(int i=0。isize。i++)//檢查它出現(xiàn)的次數(shù)是否超過數(shù)組長度的一半 if(num==numbers[i]) count++。 if(countsize/2) return num。 else return 0。 } //非遞歸形式的劃分 int partition(vectorint amp。numbers){ int size = ()。 int low = 0, high = size 1。 while(lowhigh){ int tmp = numbers[low]。//以第一個(gè)元素為標(biāo)兵 while(lowhigh){ while(lowhigh amp。amp。 numbers[high]=tmp) high。 if(low=high) break。//為了及時(shí)退出循環(huán) numbers[low] = numbers[high]。 low++。 while(lowhigh amp。amp。 numbers[low]tmp) low++。 if(low=high) break。//為了及時(shí)退出循環(huán) numbers[high] = numbers[low]。 high。 } numbers[low] = tmp。 if(low==size/2+1) break。//找到有序數(shù)組中的下標(biāo)為size/2+1的元素，結(jié)束劃分 else if(lowsize/2+1){//繼續(xù)劃分左邊 high = low 1。 low = 0。 }else{//繼續(xù)劃分右邊 low = high + 1。 high = size 1。 } } return numbers[low]。 }}。分析：為什么時(shí)間復(fù)雜度為O(n)？因?yàn)槿绻麛?shù)組元素排列是隨機(jī)的，那么每次劃分都能將數(shù)組均分為左右兩半，這樣下一次劃分的規(guī)模就縮小了一半。n+n/2+n/4+n/8+….=n(1+1/2+1/4+1/8+….)=2n。所以平均時(shí)間復(fù)雜度為O(n)。l 最小的K個(gè)數(shù)輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4。代碼：class Solution {public: vectorint GetLeastNumbers_Solution(vectorint input, int k) { vectorint vec。 int size = ()。 if(size==0 || k1 || ksize) return vec。 partition(input,k)。 for(int i=0。ik。i++) (input[i])。 return vec。 } void partition(vectorint amp。numbers, int k){ int size = ()。 int low = 0, high = size 1。 while(lowhigh){ int tmp = numbers[low]。//以第一個(gè)元素為標(biāo)兵 while(lowhigh){ while(lowhigh amp。amp。 numbers[high]=tmp) high。 if(low=high) break。//為了及時(shí)退出循環(huán) numbers[low] = numbers[high]。 low+