参考剑指offer(第二版)，这里做一个学习汇总，包括解析及代码。代码均在牛客网进行验证(摘自自己的牛客网笔记)。 整个剑指offer解析链接: 剑指offer|解析和答案(C++/Python) (一). 剑指offer|解析和答案(C++/Python) (二). 剑指offer|解析和答案(C++/Python) (三). 剑指offer|解析和答案(C++/Python) (四). 剑指offer|解析和答案(C++/Python) (五)上. 剑指offer|解析和答案(C++/Python) (五)下. 剑指offer|解析和答案(C++/Python) (六). 习题 高质量的代码 1.数值的整数次方 2.打印从1到最大的n位数 3.删除链表的节点 4.正则表达式匹配 5.表示数值的字符串 5.调整数组顺序使奇数位于偶数前面 6.链表中倒数第k个节点 7.链表中环的入口节点 8.反转链表 9.合并两个排序的链表 10.树的子结构 1.数值的整数次方 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 保证base和exponent不同时为0 思路： 在做题之前要全面考虑各种情况，包括功能测试、边界测试及负面测试。 本题拟使用全局变量来说明是否有异常情况发生：0的负指数，会造成程序出错。并且0的0次方是没有数学意义，具体返回值需提前统一。 注意：double类型不能直接用 == 进行判断相等 1.常见方法。这种思路很简单，使用循环的方式进行不断相乘，但不高效。 2.高效方法。这种方法更高效，参考公式： 使用递归求解。 代码： C++ class Solution { public:double Power(double base, int exponent) {unsigned int absExponent = (unsigned int) exponent;if(exponent < 0){absExponent = (unsigned int) -exponent;}double result = PowerWithExponent(base, absExponent);if(exponent < 0){result = 1.0/result;}return result;}double PowerWithExponent(double base, int exponent){double result ;if(exponent == 0){result = 1;return result;}if(exponent == 1){result = base;return result;}result = PowerWithExponent(base, exponent >> 1);result = result * result;if(exponent & 0x1 == 1){result = result * base;}return result;} }; Python class Solution:def Power(self, base, exponent):if exponent >= 0:absExponent = exponentelse :absExponent = -exponentresult = self.PowerWithExponent(base, absExponent)if exponent < 0:result = 1.0 / resultreturn resultdef PowerWithExponent(self, base, absExponent):if absExponent == 0:return 1if absExponent == 1:return baseresult = self.PowerWithExponent(base, absExponent >> 1)result = result * resultif absExponent & 0x1 == 1 :result = result * basereturn result 2.打印从1到最大的n位数 输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1，2，3一直到最大的3位数999。 思路： 1.n的大小没有限定，所以使用在字符串上模拟数字加法的解法。 因为数字是n位的，所以我们需要应该长度为n+1的字符串，字符串的最后一位是’\0’。当实际数字不够n位的时候，字符串前半部分补0。 Incerement函数是通过while循环，使得数字不断加1，加1的数字是最小位，即ID是length - 1对应元素。并且当数字大于10时，会产生进位，即使得takeOver = 1。takeOver 会影响前一位的数值（i - 1），并通过计算unsigned char number = (unsigned char)(numbers[i] + takeOver - ‘0’); 再次判断（i - 1）位上的数字，若（i - 1）位上的数字大于10，再进位，以此类推。直到i = 0时，这个时候若number > 10,即出现999…99(n个9)进位的情况，即溢出，则终止递增。 PrintNumbers函数是打印数组，不过需要根据阅读习惯，从第一个非0的元素开始打印。 注意：一定要使用unsigned char来声明数组，我按照剑指offer用char来声明，会有错误，我估计是因为ascii码的范围是0~255，这个范围是unsigned char的范围，不是char的范围，所以会出错。 代码：（牛客网没有这题，无法验证Python代码） C++ class Solution { public:void Print1TomaxOfNDigits(int n){if(n <= 0)return;unsigned char *numbers = new unsigned char[n + 1];int length = n + 1;for(int i = 0; i < n; ++i){numbers[i] = '0';}numbers[n] = '\0';while(!Incerement(numbers, length - 1)){PrintNumbers(numbers, length - 1);}delete[] numbers;}bool Incerement(unsigned char* numbers, int numLength){bool overFlow = false;int takeOver = 0;for(int i = numLength - 1; i >= 0; --i){unsigned char number = (unsigned char)(numbers[i] + takeOver - '0');if(i == numLength - 1){++number;}if(number >= 10){if(i == 0){overFlow = true;}else{number = number - 10;takeOver = 1;numbers[i] = '0' + number;}}else{numbers[i] = '0' + number;break;}}return overFlow;}void PrintNumbers(unsigned char* numbers, int numLength){bool beginIs0 = true;for(int i = 0; i < numLength ; ++i){if(beginIs0 && numbers[i] != '0'){beginIs0 = false;}if(!beginIs0){cout< next != nullptr){ListNode* pNext = pTOBeDeleted -> next;pTOBeDeleted -> val = pNext -> val;pTOBeDeleted -> next = pNext -> next;delete pNext;pNext = nullptr}else if(pListHead == pTOBeDeleted){delete pTOBeDeleted;pTOBeDeleted = nullptr;pListHead = nullptr;}else{ListNode* pNext = pListHead;while(pNext -> next != pTOBeDeleted){pNext = pNext -> next;}pNext -> next = nullptr;delete pTOBeDeleted;pTOBeDeleted = nullptr;}}}; 题目2：删除链表中重复的节点。 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 思路： 解决这个问题首先需要确定要删除的节点是什么。由于给了头节点，所以可以采取遍历的方法进行查找。比如使用连续两个指针，如果两个指针对应的节点的值相等，那么让第二个指针继续遍历，直到不一样，然后删除两个指针之间中间的节点（包括第一个指针），依此类推。但这样少考虑了特殊情况，因为头指针就可能是重复的节点。所以，两个指针无法解决这个问题，因此需要使用3个指针，同时在头节点之前再新建一个节点。 可以考虑以下几种特殊情况： 1——>1——>1——>1——>1——>1。1。nullptr(None)。 当新建一个节点时，就会变成： newHead——>1——>1——>1——>1——>1——>1。newHead——>1。newHead——>nullptr(None)。 那么实际返回指针便是newHead——>next，而不是pHead。因为pHead有可能被删除了。 总结：使用3个指针。使用pNode和pNext（pNode——>next）遍历链表查找重复的节点，使用pPre从newHead开始链接删除重复节点后的链表。 代码： c++ class Solution { public:ListNode* deleteDuplication(ListNode* pHead){if(pHead == nullptr)return pHead;if(pHead -> next == nullptr)return pHead;ListNode* pNewHead = new ListNode(-1);pNewHead -> next = pHead;ListNode* pNode = pHead;ListNode* pPre = pNewHead; ListNode* pNext = pNode -> next;while( pNode -> next != nullptr&& pNode != nullptr){if(pNode -> val == pNext -> val){while( pNode -> val == pNext -> val && pNext != nullptr){ListNode* temp = pNext;pNext = pNext -> next;delete temp;temp = nullptr;}delete pNode;pPre -> next = pNext;pNode = pNext;pNext = pNode -> next;}else{pPre = pNode;pNode = pNode -> next;pNext = pNode -> next;}}return pNewHead->next;} }; Python 在使用Python的时候注意： 在if或者while判断中，要先判断pNode或者pNext不等于None，才能判断pNode.val == pNext.val。如果调换顺序，由于pNext本身可能是None，则没有val属性，会报错。next同理，所以会把pNext = www.ahzjhx.com房子while循环的开头。 class Solution:def deleteDuplication(self, pHead):if pHead == None or www.ahzjhx.com == None:return pHeadpNewHead = ListNode(-1)www.ahzjhx.com = pHeadpNode = pHeadpPre = pNewHeadpNext = pNode.nextwhile pNode != None and www.ahzjhx.com != None:pNext = pNode.nextif pNode.val == pNext.val:while pNext != None and pNode.val == pNext.val: pNext = www.ahzjhx.com = pNextpNode = pNext else :pPre = pNodepNode = www.ahzjhx.com return www.ahzjhx.com 4.正则表达式匹配 请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配 思路： 思路： 由于字符匹配具有多种情况，所以本题采取递归的方式进行判罚。 主要分为两个大类： A.模式的第二个字符不是’*’ 1.若字符串的第一个字符和模式中的第一个字符相同，移位匹配下一个字符。 2.若模式中的第一个字符是’.’,则可以匹配字符串中的任意字符（’\0’是空字符，不是字符）。 3.若字符串中的第一个字符和模式中的第一个字符不相等，返回False。 B.模式的第二个字符是’*’，这种情况较复杂 1.若字符串的第一个字符和模式中的第一个字符相同或者若模式中的第一个字符是’.’,则可以匹配字符串中的任意字符，则有3种情况： （1）字符串和模式均移位：str + 1， pattern + 2。 （2）忽略模式中’*‘前的字符（’*‘前面的字符可以出现任意次，含0次）：str, pattern + 2。 （3）让模式中的’*‘前的字符重复一次（’‘前面的字符可以出现任意次）：str + 1， pattern。 2.若字符串的第一个字符和模式中的第一个字符不同，且模式中的第一个字符不是’.’：str， pattern + 1。 递归的边界条件： 1.当str和pattern都同时遍历完，则返回True。 2.当str没有遍历完，pattern遍历完，则返回False。 （3.当str遍历完，而pattern没有遍历完，不是边界条件，考虑特殊情况’’,’.*’,以及’’,’’。这两个例子均是True。） 代码： C++ class Solution { public:bool match(char* str, char* pattern){if(str == nullptr|| pattern == nullptr){return false;}return matchCore(str, pattern);}bool matchCore(char* str, char* pattern){if(*str == '\0' && *pattern == '\0'){return true;}if(*str != '\0' && *pattern == '\0'){return false;}if(*str == '\0' && *pattern != '\0'){return false;}if(*(pattern + 1) == '*'){if(*pattern == *str || (*pattern == '.' && *str != '\0')){return matchCore(str + 1, pattern + 2)|| matchCore(str + 1, pattern)|| matchCore(str, pattern + 2);}else{return matchCore(str, pattern + 2);}}if(*str == *pattern || (*pattern == '.' && *str != '\0')){return matchCore(str + 1, pattern + 1);}return false; } }; Python： python需要注意：Python不支持单字符类型，单字符在 Python 中也是作为一个字符串使用。字符串中没有 ‘\0’。为了避免 string index out of range 需有使用len()对其判断。 class Solution:def match(self, s, pattern):if s == None or pattern == None:return Falsereturn self.matchCore(s, pattern)def matchCore(self, s, pattern):if len(s) == 0 and len(pattern) == 0:return Trueif len(s) > 0 and len(pattern) == 0:return Falseif len(pattern) > 1 and pattern[1] == '*':if len(s) > 0 and ( s[0] == pattern[0] or pattern[0] == '.' ):return self.matchCore(s[1:], pattern[2:]) \or self.matchCore(s, pattern[2:]) \or self.matchCore(s[1:], pattern)else :return self.matchCore(s, pattern[2:])if len(s) > 0 and ( s[0] == pattern[0] or pattern[0] == '.' ):return self.matchCore(s[1:], pattern[1:])return False 5.表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。 思路： 这个题注意注意一些条件，以遍历整个字符串的方式进行判断。 写的时候可以参考通式： +/- A . B e/E +/- C 1.A 、 B 、C的判断方式是一样的，即判断全是数字组成即可。 2.+/- 只能出现在A 和C的前面 且只能出现一次。 3. 小数点. 只能出现一次，可以是： （a）A.，小数点后面可以没有整数部分。 （b）.B, 小数点前面可以没有整数部分。 （c）A.B, 小数点前后都可以有数字。 4.指数E/e： （a）e/E前面必须有数字，.e1,e2不能表示数字。 （b）e/E后面必须有数字，且不能有小数点，1e，e+1.1不能表示数字。 因此使用函数scanUnsignedInteger扫描数字（A、B、C），当遇到小数点’.'或者’e’以及’E’时，跳出，进行逻辑判断。 代码： C++ class Solution { public:bool isNumeric(char* string){bool flagDouHao = true;bool flagENum = false;if(string == nullptr)return false;if(*string == '+' || *string == '-'){++string;}if(*string == '.'){++string;flagDouHao = false;}char* before = string;char* after = scanUnsignedInteger(string);string = after;bool numeric = before < after;if(before < after)flagENum = true;if(*string == '.'){++string;numeric = numeric && flagDouHao;}else if(*string == 'e' || *string == 'E'){++string;if(*string == '+' || *string == '-')++string;char* before = string;char* after = scanUnsignedInteger(string);string = after;numeric = numeric && (before < after) && flagENum;return numeric && (*string == '\0');}if(*string =='\0'){numeric = numeric && true;}else{char* before = string;char* after = scanUnsignedInteger(string);string = after;if(before < after)flagENum = true;numeric = numeric && (before < after);}if(*string =='e' || *string =='E'){++string;if(*string == '+' || *string == '-')++string;char* before = string;char* after = scanUnsignedInteger(string);string = after;numeric = numeric && (before < after) && flagENum;}return numeric && (*string == '\0');}char* scanUnsignedInteger(char* str){while(*str != '\0' && *str >= '0' && *str <= '9'){++str;}return str;} }; Python： python只能用len()来进行判断字符串是否结束。 class Solution:def isNumeric(self, s):flagDouHao = TrueflagENum = Falseif len(s) == 0:return Falseif len(s) > 0 and (s[0] == '+' or s[0] == '-'):s = s[1:]if len(s) > 0 and s[0] == '.':s = s[1:]flagDouHao = False before = len(s)s = self.scanUsignedNum(s) after = len(s)numeric = (before > after)if before > after:flagENum = Trueif len(s) > 0 and s[0] == '.':s = s[1:]elif len(s) > 0 and (s[0] == 'e' or s[0] == 'E' ):s = s[1:]if len(s) > 0 and (s[0] == '+' or s[0] == '-'):s = s[1:] before = len(s)s = self.scanUsignedNum(s)after = len(s)numeric = (before > after) and flagENum return numeric and len(s) == 0 if len(s) == 0:numeric = numeric and Trueelse :before = len(s)s = self.scanUsignedNum(s) after = len(s)numeric = (before > after) and flagDouHaoif before > after:flagENum = Trueif len(s) > 0 and (s[0] == 'e' or s[0] == 'E' ):s = s[1:]if len(s) > 0 and (s[0] == '+' or s[0] == '-'):s = s[1:] before = len(s)s = self.scanUsignedNum(s)after = len(s)numeric = (before > after) and flagENum return numeric and len(s) == 0def scanUsignedNum(self, s):for i in range(len(s)):if s[i] <='9' and s[i] >= '0':continueelse :return s[i:]return s[len(s):] 5.调整数组顺序使奇数位于偶数前面 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 思路： 思路： 如果本题没有要求“奇数和奇数，偶数和偶数之间的相对位置不变”，那么会有优化思路： 设置两个指针，一个在头，一个在尾，无非以下四种情况。 1.头：奇数（右移） 尾：偶数（左移）。 2.头：奇数（右移） 尾：奇数（不变）。 3.头：偶数（交换） 尾：奇数（交换）。 4.头：偶数（不变） 尾：偶数（左移）。 知道头指针地址>尾指针地址。 不过在牛客网上有限制条件：“奇数和奇数，偶数和偶数之间的相对位置不变”，因此上述优化方法无效，现提出两种方法。 1.新建一个向量（列表），使用额外内存开销，直接存储奇数和偶数。 代码： C++ class Solution { public:void reOrderArray(vector &array) {int length = array.size();vector arr;for(int i = 0; i < length; ++i){if((array[i] & 0x01) == 1)arr.push_back(array[i]);}for(int i = 0; i < length; ++i){if((array[i] & 0x01) != 1)arr.push_back(array[i]);}array.swap(arr);} }; Python class Solution:def reOrderArray(self, array):arr = []for i in range(len(array)):if array[i] & 0x1 == 1:arr.append(array[i])for i in range(len(array)):if array[i] & 0x1 == 0:arr.append(array[i]) return arr 或 class Solution:def reOrderArray(self, array):odd,even=[],[]for i in array:odd.append(i) if i%2==1 else even.append(i)return odd+even 2.使用类似冒泡排序的算法，时间复杂度O(n^2),如果遇到偶奇排序，直接交换两个数字。 C++ class Solution { public:void reOrderArray(vector &array) {int length = array.size();for(int i = 0; i < length - 1; ++i){for(int j = 0; j < length - 1 - i; ++j){if((array[j]&0x01) == 0 && (array[j + 1]&0x01) != 0){int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}} }; Python class Solution:def reOrderArray(self, array):for i in range(len(array)):for j in range(len(array) - 1 - i):if (array[j] & 0x1) == 0 and (array[j + 1] & 0x1) == 1:temp = array[j]array[j] = array[j + 1]array[j + 1] = tempreturn array 6.链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个结点。 备注：为符合大多数人习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如一个链表有6个节点，从头节点开始，它们的值依次是1,2,3,4,5,6。这个链表的倒数第3个节点是值为4的节点。 思路： 由于题目链表是单向链表，所以不能采取先走到链表的尾端，再从尾端回溯到k步。 设置两个指针pFirst和pSecond。如图所示： （a）pFirst先走k - 1步。 （b）pSecond指向头指针。 （c）pFirst和pSecond在第k步时同时移动，直到pFirst指向尾节点。 这种方法简单高效，只需要遍历一次即可。 但为了保证代码的鲁棒性需要注意： 1.输入的头指针pListHead不能为空指针，否则代码会试图访问空指针指向的内存，造成程序崩溃。 2.输入的已pListHead为头节点的链表总数不能少于k，否则会由于在for循环中会在链表上向前走k - 1步，仍然会由于空指针造成程序崩溃。 3.输入的参数k不能为0，由于k是一个无符号整数，那么在for循环中k - 1得到的将不是 -1，而是4294967295（无符号的0xFFFFFFFF）。因此for循环执行的次数会远远超出预计，同样造成奔溃。 代码： C++： class Solution { public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(k == 0 || pListHead == nullptr){return nullptr;}ListNode* pFirst = pListHead;ListNode* pSecond = pListHead;for(unsigned int i = 0; i < k - 1; ++i){if(pFirst -> next != nullptr){pFirst = pFirst -> next;}else{return nullptr;}}while(pFirst -> next != nullptr){pFirst = pFirst -> next;pSecond = pSecond -> next;}return pSecond;} }; Python： class Solution:def FindKthToTail(self, head, k):if k == 0 or head == None:return NonepFirst = headpSecond = headfor i in range(k - 1):if www.ahzjhx.com != None:pFirst = pFirst.nextelse :return Nonewhile www.ahzjhx.com != None:pFirst = pFirst.nextpSecond = pSecond.nextreturn pSecond 7.链表中环的入口节点 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 思路： 这个问题分3步走： 1.首先判断链表中是否有环存在。使用两个指针，一个快，一个慢，同时从头节点出发，若在链表中相遇，则存在环。若快指针先遍历完（pFast->next = nullptr），则链表中不存在环。 2.若存在环，则判断环中有多少个节点。返回第一步相遇的指针pFast，从pFast开始计数，直到再次返回到pFast的初始位置，则计数值为环节点的数目为numNodes。 3.判断环的入口节点。根据第2步得到的环节点数目，生成两个指针pFirst和pSecond，pFirst先移动numNodes步，接下来pFirst和pSecond同时移动，直到相遇。相遇的节点即为环的入口节点。 参考图示： 代码： C++： class Solution { public:ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode* meetNode = MeetingNode(pHead);if(meetNode == nullptr)return nullptr;int numNode = 1;ListNode* pNode = meetNode;while(pNode -> next != meetNode){pNode = pNode -> next;++numNode;}ListNode* pFirst = pHead;ListNode* pSecond = pHead;for(int i = 0; i < numNode; ++i){pFirst = pFirst -> next;}while(pFirst != pSecond){pFirst = pFirst -> next;pSecond = pSecond -> next;}return pFirst;}ListNode* MeetingNode(ListNode* pHead){ListNode* pSlow = pHead;ListNode* pFast = pHead;if(pHead == nullptr){return nullptr;}if(pSlow -> next != nullptr){pFast = pFast -> next;}while(pFast -> next != nullptr){if(pSlow == pFast)return pFast;pSlow = pSlow -> next;pFast = pFast -> next;if(pFast -> next != nullptr)pFast = pFast -> next;}return nullptr;} }; Python： class Solution:def EntryNodeOfLoop(self, pHead):meetNode = self.MeetingNode(pHead)if meetNode == None:return NonenumNodes = 1pNode = meetNodewhile www.ahzjhx.com != meetNode:pNode = pNode.nextnumNodes = numNodes + 1pFirst = pHeadpSecond = pHeadfor i in range(numNodes):pFirst = pFirst.nextwhile pFirst != pSecond:pFirst = pFirst.nextpSecond = pSecond.nextreturn pFirstdef MeetingNode(self, pHead):if pHead == None:return NonepSlow = pHeadpFast = pHeadif www.ahzjhx.com == None:return NonepFast = www.ahzjhx.com while www.ahzjhx.com != None:if pSlow == pFast:return pFastpSlow = pSlow.nextpFast = pFast.nextif www.ahzjhx.com != None:pFast = pFast.nextreturn None 8.反转链表 输入一个链表，反转链表后，输出新链表的表头。 思路： 先对链表进行判断，如果链表是空或者链表只有一个节点，则直接返回该链表。如果链表节点大于等于2个，则使用三个指针来完成。 容易出现的问题： 1.输入的链表头为nullptr或者整个链表只有一个节点，程序立即崩溃。 2.反转后的链表出现断裂。 3.返回的反转之后的头节点不是原始链表的尾节点。 测试用例： 1.输入的链表头指针是nullptr。 2.输入的链表只有一个节点。 3.输入的链表有多个节点。 参考图示： 代码： C++： class Solution { public:ListNode* ReverseList(ListNode* pHead) {if(pHead == nullptr || pHead -> next == nullptr){return pHead;}ListNode* pReverseHead = nullptr;ListNode* pNode = pHead;ListNode* pPre = nullptr;while(pNode -> next != nullptr){pReverseHead = pNode -> next;pNode -> next = pPre;pPre = pNode;pNode = pReverseHead;}pReverseHead -> next = pPre;return pReverseHead;} }; Python class Solution:def ReverseList(self, pHead):if pHead == None or www.ahzjhx.com == None:return pHeadpNode = pHeadpReverHead = NonepPre = Nonewhile www.ahzjhx.com != None:pReverHead = www.ahzjhx.com = pPrepPre = pNodepNode = www.ahzjhx.com = pPrereturn pReverHead 9.合并两个排序的链表 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 思路： 参考图示： 1.先找到两个链表中头节点，把值较小的的节点取出。 2.再继续比较剩余两个链表的头节点，把值较小的的节点取出。 3.重复上述步骤，直到某一个链表为空（NULL/nullptr） 代码： C++： class Solution { public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if(pHead1 == NULL && pHead2 != NULL){return pHead2;}else if(pHead1 != NULL && pHead2 == NULL){return pHead1;}else if(pHead1 == NULL && pHead2 == NULL){return NULL;}ListNode* pMergeHead = NULL;if(pHead1 -> val <= pHead2 -> val){pMergeHead = pHead1;pMergeHead -> next = Merge(pHead1 -> next, pHead2);}else{pMergeHead = pHead2;pMergeHead -> next = Merge(pHead1, pHead2 -> next);}return pMergeHead;} }; Python class Solution:def Merge(self, pHead1, pHead2):if pHead1 == None and pHead2 != None:return pHead2if pHead1 != None and pHead2 == None:return pHead1if pHead1 == None and pHead2 == None:return NonepMergeHead = Noneif pHead1.val <= pHead2.val:pMergeHead = www.ahzjhx.com = self.Merge(www.ahzjhx.com, pHead2)else:pMergeHead = www.ahzjhx.com = self.Merge(pHead1, www.ahzjhx.com)return pMergeHead 10.树的子结构 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 思路： 使用递归操作，分为两步： 1.在树A中找到和树B根节点的值一样的节点R。 2.判断A树中以R为根节点的子树是不是包含和树B一样的结构。 3.若是返回Ture，若不是继续遍历树A左右节点，寻找和树B根节点的值一样的节点R。 参考图示： 注意： 1.需要检查边界条件，即检查空指针，否则程序容易崩溃。 2.如果树中的节点值是double/float型，则不能使用pRoot1 -> val == pRoot2 -> val，这是因为计算机内表示小数时都存在误差。判断两个小数是否相等，只能判断它们之间的绝对值是不是在一个很小的范围内。参考代码： bool Equal(double num1, double num2){if((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))return true;elsereturn false; } 代码： C++ class Solution { public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){bool isTree = false;if(pRoot1 == NULL || pRoot2 == NULL){return false;}if(pRoot1 -> val == pRoot2 -> val){isTree = doesTreeHasTree2(pRoot1, pRoot2);}isTree = HasSubtree(pRoot1 -> left, pRoot2)|| HasSubtree(pRoot1 -> right, pRoot2) || isTree;return isTree;}bool doesTreeHasTree2(TreeNode* pRoot1, TreeNode* pRoot2){if(pRoot2 == NULL){return true;}if(pRoot1 == NULL){return false;}if(pRoot1 -> val == pRoot2 -> val){return doesTreeHasTree2(pRoot1 -> left, pRoot2 -> left)&& doesTreeHasTree2(pRoot1 -> right, pRoot2 -> right);}return false;} }; Python class Solution:def HasSubtree(self, pRoot1, pRoot2):isTree = Falseif pRoot1 == None or pRoot2 == None:return Falseif pRoot1.val == pRoot2.val:isTree = self.doesTreeHasTree2(pRoot1, pRoot2)isTree = self.HasSubtree(pRoot1.left, pRoot2) \or self.HasSubtree(pRoot1.right, pRoot2) \or isTreereturn isTreedef doesTreeHasTree2(self, pRoot1, pRoot2):if pRoot2 == None:return Trueif pRoot1 == None:return Falseif pRoot1.val == pRoot2.val:return self.doesTreeHasTree2(pRoot1.left, pRoot2.left) \and self.doesTreeHasTree2(pRoot1.right, pRoot2.right)return False