devbox
tf789
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

剑指 offer 编程题 C++ 版总结(下)

作者：tf789 | 2024-01-29 17:13:22

赞

踩

剑指 offer 编程题 C++ 版总结(下)

解题思路：让两个指针分别指向两个链表，当遍历到最末尾的结点后，指针指向另一个链表的头结点。例如：A 和 B 开始的时候分别指向 4 和 5。两个指针分别遍历链表，当 A 遍历到末尾结点的 5 时，下一步让其指向头结点为 5 的结点。而 B，让其指向头结点为 4 的结点。这样，A 和 B 指针在指向公共结点的时候都走了相同的距离，所以它们相遇的时候该结点就是公共结点。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  12.         ListNode *node1 = headA;
  13.         ListNode *node2 = headB;
  14.         
  15.         while (node1 != node2) {
  16.             if(node1 != NULL)
  17.                 node1 = node1->next;
  18.             else
  19.                 node1 = headB;
  20.             if(node2 != NULL)
  21.                 node2 = node2->next;
  22.             else
  23.                 node2 = headA;
  24.         }
  25.         return node1;
  26.     }
  27. };

解题思路：由题可知，数组是排好序的，所以可以先用二分查找找出 target 所在的下标，然后根据下标向前向后查找即可。

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.             int count = 0, mid, low = 0, high = nums.size()-1;
  5.             
  6.             while(low <= high)
  7.             {
  8.                 mid = low + (high - low)/2;
  9.                 if(nums[mid] == target){
  10.                     count = searchcount(nums, target, mid);
  11.                     break;
  12.                 }
  13.                 else if(nums[mid] < target)
  14.                     low = mid + 1;
  15.                 else
  16.                     high = mid - 1;
  17.             }
  18.             return count;
  19.     }
  20.     int searchcount(vector<int>& nums, int target, int index)
  21.     {
  22.         int count = 0, left = index - 1, right = index + 1;
  23.         while( left >= 0 ) {
  24.             if(nums[left--] == target)
  25.                 count++;
  26.             else 
  27.                 break;
  28.         }
  29.         while( right < nums.size() ) {
  30.             if(nums[right++] == target)
  31.                 count++;
  32.             else 
  33.                 break;
  34.         }
  35.         return count + 1;
  36.     }
  37. };

解题思路：是有序数组，第一个想到的就是二分查找。

  1. class Solution {
  2. public:
  3.     int missingNumber(vector<int>& nums) {
  4.         int left = 0, right = nums.size();
  5.         while(left < right){
  6.             int mid = left + (right - left)/2;
  7.             if(mid == nums[mid]){
  8.                 left = mid+1;
  9.             }else{
  10.                 right = mid;
  11.             }
  12.         }
  13.         return left;
  14.     }
  15. };

解题思路：二叉搜索树中序遍历可以得到递增有序序列。将二叉树中序非递归遍历反向操作，每次先右子树入栈即可获得递减有序序列。这样就能很快找到第 k 大的结点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int kthLargest(TreeNode* root, int k) {
  13.             stack<TreeNode*> sta;
  14.             TreeNode* p = root;
  15.             int count = 0, result;
  16.             while(!sta.empty() || p != NULL)
  17.             {
  18.                 while(p)
  19.                 {
  20.                     sta.push(p);
  21.                     p = p->right;
  22.                 }
  23.                 p = sta.top();
  24.                 if(++count == k)
  25.                     result = p->val;
  26.                 sta.pop();
  27.                 p = p->left;
  28.             }
  29.         return result;
  30.     }
  31. };

解题思路：利用递归计算二叉树的深度。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int maxDepth(TreeNode* root) {
  13.             if(root == NULL)
  14.                 return 0;
  15.             int i = maxDepth(root->left);
  16.             int j = maxDepth(root->right);
  17.  
  18.             return i > j ? i+1: j+1;
  19.     }
  20. };

解题思路：利用递归计算二叉树的深度。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool isBalanced(TreeNode* root) {
  13.         return !root ? true : abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
  14.     }
  15.     int depth(TreeNode* cur) { //计算二叉树的最大深度
  16.         return !cur ? 0 : max(depth(cur->left), depth(cur->right)) + 1;
  17.     }
  18. };

解题思路：(1) 用哈希表。(2) 题目中强调其他数字出现两次，如果只有一个数字的情况下，我们可是使用异或（相同为0，不同为1）得出要找的数字。但是题中要找的数数字有两个，所以这个时候还是需要对整个序列求异或。这样最终得到的是要找的两个数字的异或的结果。此时，我们可以根据得到的值，将原本序列分成两个序列（每个序列除了一个单独数字外，其余的数字都是成对出现的），然后再对这两个序列进行异或操作就能找出两个只出现一次的数字。

  1. class Solution {
  2. public:
  3.     vector<int> singleNumbers(vector<int>& nums) {
  4.         unordered_map<int, int> res;
  5.         vector<int> number;
  6.         for (int i = 0; i < nums.size(); i++) {
  7.             res[nums[i]]++;
  8.         }
  9.         for (auto c : nums) {
  10.             if (res[c] == 1) {
  11.                 number.emplace_back(c);
  12.             }
  13.         }
  14.         return number;
  15.     }
  16. };
  17.  
  18.  
  19. class Solution {
  20. public:
  21.     vector<int> singleNumbers(vector<int>& nums) {
  22.         //总共分为两个步骤：(1) 整个序列求异或   (2) 根据异或值划分序列后再求异或
  23.         //第一步：求所有的数异或的结果
  24.         int k = 0;
  25.         for (int num : nums) {
  26.             k ^= num;
  27.         }
  28.         //获得k中最低位的1,k里面两数不同，故肯定有一位1是不同的，可以以此区分两个序列
  29.         int mask = 1;
  30.         while ((k & mask) == 0) {
  31.             mask <<= 1;
  32.         }
  33.         int a = 0; 
  34.         int b = 0;
  35.         //第二步：根据 mask 划分序列后再求异或
  36.         for (int num : nums) {
  37.             if ((num & mask) == 0) {
  38.                 a ^= num;  // 找到那位不为1的元素， 其余数为偶数，会自动消去
  39.             } else {
  40.                 b ^= num;  // 找到那位为1的元素
  41.             }
  42.         }
  43.         return {a, b};
  44.     }
  45. };

解题思路：(1) 用哈希表。(2) 使用位运算。得注意的是：如果某个数字出现 3 次，那么这个 3 个数字的和肯定能被 3 整除，则其对应二进制位的每一位的和也能被 3 整除。统计数组中每个数字的二进制中每一位的和，判断该和是否能被 3 整除。若可以，则只出现一次的数字的二进制数中那一位为 0，否则为 1。

  1. class Solution {
  2. public:
  3.     int singleNumber(vector<int>& nums) {
  4.         unordered_map<int, int> mp;
  5.         for(int n : nums) mp[n] ++;
  6.         int ans;
  7.         for(auto pr : mp){
  8.             if(pr.second == 1){
  9.                 ans = pr.first;
  10.                 break;
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. };
  16.  
  17.  
  18. class Solution {
  19. public:
  20.     int singleNumber(vector<int>& nums) {
  21.         int ans = 0;
  22.         for(int i = 0; i < 32; ++i){
  23.             int cnt = 0;
  24.             for(int n : nums){
  25.                 // n & 1 << i 的值大于0即为真
  26.                 if(n & (1 << i)) cnt++;
  27.             }
  28.             // 构造只出现一次的那个数字，采用异或的方法生成二进制中的每一位
  29.             if(cnt % 3 == 1) ans ^= (1 << i);
  30.         }
  31.         return ans;
  32.     }
  33. };

解题思路：题中所给的序列是递增排序序列，所以可以使用双指针 low 和 high 解决该问题。若 low 和 high 的两个元素相加为 target 此时记录相应的值返回即可。若两者的和大于 target，令 high--。反之令 low++。

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.             int size = nums.size();
  5.             vector<int> asd(2, 0); 
  6.             int low = 0, high = size-1;
  7.             while(low < high)
  8.             {
  9.                 if(nums[low] + nums[high] == target){   
  10.                     asd[0] = nums[low];
  11.                     asd[1] = nums[high];
  12.                 }
  13.                 if(nums[low] + nums[high] > target){
  14.                     high--;
  15.                 }
  16.                 else{
  17.                     low++;
  18.                 }
  19.             }
  20.             return asd;
  21.     }
  22. };

解题思路：该题所求的是所有和为 target 的连续正整数序列的组合。这里可以使用暴力枚举解决该题。首先需要确定边界，limit 为 target / 2 向下取整。内层循环完成累加操作，若累加和等于 target，则记录相应的数字序列。循环终止的条件是累加和大于 target。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> findContinuousSequence(int target) {
  4.         vector<vector<int>> vec;
  5.         vector<int> res;
  6.         int sum = 0, limit = (target - 1) / 2; //(target - 1)/2 等效于 target / 2 下取整
  7.         for (int i = 1; i <= limit; ++i) {
  8.             for (int j = i;; ++j) {
  9.                 sum += j;                      //完成累加操作
  10.                 if (sum > target) {
  11.                     sum = 0;
  12.                     break;
  13.                 }
  14.                 else if (sum == target) {      //记录数字序列
  15.                     res.clear();
  16.                     for (int k = i; k <= j; ++k) res.emplace_back(k);
  17.                     vec.emplace_back(res);
  18.                     sum = 0;
  19.                     break;
  20.                 }
  21.             }
  22.         }
  23.         return vec;
  24.     }
  25. };

下面这个方法是对上述代码的改进。每次操作之后的序列和操作之前的序列相比大部分数字都是一样的，只是增加或减少了一个数字，因此我们可以在前一个序列的和的基础上求操作之后的序列的和。这样可以减少很多不必要的运算，从而提高代码效率。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> findContinuousSequence(int target) {
  4.         vector<vector<int>> result;
  5.         vector<int> asd;
  6.         if(target < 3)
  7.             return result;
  8.         int low = 1, high = 2;
  9.         int middle = (target+1)/2;
  10.         int sum = low + high;
  11.         while(low < middle)
  12.         {
  13.             if(sum == target)
  14.             {
  15.                 Add(result, asd, low, high);
  16.             }
  17.  
  18.             while(sum > target && low < middle)
  19.             {
  20.                 sum -= low;
  21.                 low++;
  22.                 if(sum == target)
  23.                 {
  24.                     Add(result, asd, low, high);
  25.                 }   
  26.             }
  27.  
  28.             high++;
  29.             sum += high;
  30.         }
  31.         return result;
  32.     }
  33.     void Add(vector<vector<int>>& result, vector<int>& asd, int low, int high)
  34.     {
  35.         for(int i = low; i <= high ; i++)
  36.             asd.push_back(i);
  37.         result.push_back(asd);
  38.         asd.clear();
  39.     }
  40. };

若上面的题目不要求组合内的序列是连续的，那该怎么解决？

  1. #include <iostream>
  2. #include <list>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. int *a, *b, N, n;
  7. int total = 0;
  8. void find(int sum, int n, int b[])
  9. {
  10. 	//递归出口
  11. 	if(sum <= 0 || n <= 0)
  12. 		return;
  13.  
  14. 	//输出找到的结果
  15. 	if(sum == b[n-1])    //表示找到了一个值
  16. 	{
  17. 		a[n-1] = 1;
  18. 		for(int i = 0; i < N; i++)
  19. 		{
  20. 			if(a[i] == 1)
  21. 				cout << b[i] <<" ";
  22. 		}
  23. 		cout <<endl;
  24. 		total++;
  25. 	}
  26.  
  27. 	a[n-1] = 1;
  28. 	find(sum-b[n-1], n-1, b);    //如果放入n，则从剩余n-1个数中填满sum-n
  29. 	a[n-1] = 0;
  30. 	find(sum, n-1, b);           //如果不放入n，从n-1个数中填满sum
  31. }
  32.  
  33. int main()
  34. {
  35. 	int sum;
  36. 	cout<<"Please Input n&sum:"<<endl;
  37. 	cin>>N>>sum;
  38. 	a = new int[N];
  39. 	b = new int[N];
  40. 	for(int i = 0; i < N; i++)
  41. 		cin >> b[i];
  42. 	n = N;
  43. 	find(sum, n, b);
  44. 	cout<<"Total:"<<total<<endl;
  45. 	//cout << Number <<endl;
  46.     delete []a;
  47.     delete []b;
  48. 	return 0;
  49. }

解题思路：(1) 该题是利用空格进行划分，所以可以使用双指针从后往前将字符串进行分割。 (2) 利用 strtok 函数对字符串进行分割，利用 vector 存储分割后的单词，接着完成一个 reverse 操作。最后根据题意，添加相应的空格即可。

  1. class Solution {
  2. public:
  3.     string reverseWords(string s) {
  4.         string str;
  5.         if(s.empty())  //输入字符为空，返回空
  6.             return str;
  7.         cout << s.size() <<endl;
  8.         int i{0}, j{0};  //i，j用来表示单词开始和结束的位置
  9.         j = s.size() - 1;
  10.         for(j; j >= 0; --j)
  11.         {
  12.             if(s[j] != ' ')  //遇到不是空格的
  13.             {
  14.                 i = j;
  15.                 while(i >=0 && s[i] != ' ')  //从j开始向左寻找单词，i>=0防止越界访问
  16.                     --i;
  17.                 for(int k = i + 1; k <= j; ++k)  //单词序列加入字符串中
  18.                     str.push_back(s[k]);
  19.                 str.push_back(' ');  //加入一个空格
  20.                 j = i;  //改变j的位置
  21.             }
  22.         }
  23.         if(str.size() > 0)
  24.             str.pop_back();  //移除末尾空格
  25.         return str;
  26.     }
  27. };
  28.  
  29.  
  30. class Solution {
  31. public:
  32.     string reverseWords(string s) {
  33.             vector<string> asd;
  34.             int size = s.size();
  35.             char* p = new char[size+1];
  36.             strcpy(p, s.c_str());
  37.             char* token = strtok(p, " ");
  38.             while(token != NULL){
  39.                 asd.push_back(token);
  40.                 token = strtok(NULL, " ");
  41.             }
  42.             reverse(asd.begin(), asd.end());
  43.             string result;
  44.             for(int i = 0; i < asd.size(); i++){
  45.                 if(i != asd.size()-1)
  46.                     result += asd[i] + " ";
  47.                 else
  48.                     result += asd[i];
  49.             }
  50.             delete []p;
  51.             return result;
  52.     }
  53. };

  1. class Solution {
  2. public:
  3.     string reverseLeftWords(string s, int n) {
  4.         reverse(s.begin(), s.begin() + n);
  5.         reverse(s.begin() + n, s.end());
  6.         reverse(s.begin(), s.end());
  7.         return s;
  8.     }
  9. };

解题思路：直接根据题意做题，用变量记录划窗中的最大值和其下标。当划窗移动的时候，先判断最值下标是否在区间内。如果在，只用对比新添加的元素和最值的大小即可。如果不在，就需要重新寻找划窗中的最大值了。

  1. class Solution {
  2. public:
  3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  4.         vector<int>a;
  5.         if(nums.size() == 0){      
  6.             return a;
  7.         }
  8.         int n = nums.size() - k + 1; // 滑动窗口滚动的次数
  9.         int t = -1;                  // 当前滑窗最大值的下标
  10.         int max;                     // 当前滑窗最大值
  11.  
  12.         // 遍历，找每个滑窗的最大值
  13.         for(int i = 0;i < n ;i++){
  14.             // 上个滑窗的最大值还在当前滑窗内，如果新加入的元素比最大值还大，更新最大值和其下标     
  15.             if(t >= i){
  16.                 if(nums[i+k-1] >= max){
  17.                     t = i+k-1;
  18.                     max = nums[i+k-1];
  19.                 }
  20.             }
  21.             // 不在的时候重新遍历当前滑窗，这里效率就低
  22.             else{
  23.                 max = nums[i];
  24.                 for(int j = i + 1;j < k + i;j++){
  25.                     if(nums[j] >= max){
  26.                         t = j;
  27.                         max = nums[j];
  28.                     }
  29.                 }
  30.             }
  31.             // 添加最大值
  32.             a.push_back(max);
  33.         }
  34.         return a;
  35.     }
  36. };

解题思路：解决该题需要用到两个数据结构，queue 和 deque，其中 queue 用于存储数据，deque 用于记录序列的最大值。

push_back()：当添加一个新的数据的时候，如果 deque 不为空的情况下且其中的值小于添加的值，那么就将 deque 中的数据 pop_back()，然后将数据同时添加到 deque 和 queue 中。

pop_front()：正常 pop 队列元素即可。需要添加的代码是，如果 queue 和 deque 队首元素相等，则两个都要 pop 元素。

max_value()：deque 为空时 return -1 ，不为空时 return deque 的队首元素。

  1. class MaxQueue {
  2.     queue<int> q;
  3.     deque<int> d;
  4. public:
  5.     MaxQueue() {
  6.     }
  7.     
  8.     int max_value() {
  9.         if (d.empty())
  10.             return -1;
  11.         return d.front();
  12.     }
  13.     
  14.     void push_back(int value) {
  15.         while (!d.empty() && d.back() < value) {
  16.             d.pop_back();
  17.         }
  18.         d.push_back(value);
  19.         q.push(value);
  20.     }
  21.     
  22.     int pop_front() {
  23.         if (q.empty())
  24.             return -1;
  25.         int ans = q.front();
  26.         if (ans == d.front()) {
  27.             d.pop_front();
  28.         }
  29.         q.pop();
  30.         return ans;
  31.     }
  32. };

解题思路：有一串连续的数字（无重复），这串数字中最大值为 m，最小值为 n，这串数字一共包含 m-n+1 个数字。同样，如果我们能够知道 5 张扑克牌中的最大值 maxValue 和最小值 minValue，那我们就知道，要使它为顺子需要 maxValue - minValue + 1 张牌。

(1) 在查找 maxValue 和 minValue 过程中，跳过大小王。

(2) 如果 maxValue - minValue + 1 > 5，说明题目给的 5 张牌不足以构成顺子，即使里面有大小王，也不够用来填补使它构成顺子，所以返回 false。

(3) 如果 maxValue - minValue + 1 <= 5，说明 5 张牌足以构成顺子（里面的大小王能填补在合适位置），返回 true。

  1. class Solution {
  2. public:
  3.     bool isStraight(vector<int>& nums) {
  4.         bool m[15];
  5.         memset(m, 0, sizeof(m));
  6.         int minValue = 14, maxValue = 0;
  7.         for (int item : nums) {
  8.             if (item == 0) {
  9.                 continue;
  10.             }
  11.             if (m[item]) {
  12.                 return false;
  13.             }
  14.             m[item] = true;
  15.             minValue = min(minValue, item);
  16.             maxValue = max(maxValue, item);            
  17.         }
  18.         return maxValue - minValue + 1 <= 5;
  19.     }
  20. };

解题思路：这个问题实际上是约瑟夫问题。下面这个例子是N=8 m=3的例子。我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关系最后剩下来这个人的索引号的变化情况即可。

现在我们知道了G的索引号的变化过程，那么我们反推一下从N = 7 到N = 8 的过程。我们先把被删除的C补充回来，然后右移m个人，发现溢出了，再把溢出的补充在最前面，经过这个操作就恢复了N = 8 的排列了！

因此我们可以推出递推公式 f(8,3) = [ f(7, 3) + 3 ] % 8。进行推广泛化，即 f(n,m) = [ f(n−1,m) + m ]%n 。

  1. 法一：递推公式
  2. class Solution {
  3. public:
  4.     int lastRemaining(int n, int m) {
  5.         int pos = 0;             // 最终留下的初始位置
  6.         for(int i = 2; i <= n; i++){
  7.             pos = (pos + m) % i;  // 每次循环右移
  8.         }
  9.         return pos;
  10.     }
  11. };
  12.  
  13. 法二：用链表
  14. int lastRemaining(int n, int m)
  15. {   // n个数字，每次删除第m个数字
  16. 		if(n < 1 || m < 1)
  17. 			return -1;
  18. 			
  19. 		int i = 0;
  20. 		list<int> a;
  21. 		for(i = 0; i < n; i++)
  22. 			a.push_back(i);
  23. 			
  24. 		list<int>::iterator current = a.begin();
  25. 		list<int>::iterator next;
  26. 		
  27. 		while(a.size() > 1){
  28. 			for(int i = 1; i < m; i++)
  29. 			{
  30. 				current++;
  31. 				if(current == a.end())
  32. 					current = a.begin();
  33. 			}
  34. 			next = ++current;
  35. 			if(next == a.end())
  36. 				next = a.begin();
  37. 				
  38. 			--current;
  39. 			a.erase(current);
  40. 			current = next; 
  41. 		}//end while
  42. 		
  43. 		return *(current);
  44. }

解题思路：最简单的办法是使用两层循环解决该问题，即外层循环从 0 开始，内层循环使用一个变量记录循环过程中最大的利润。这样算法复杂度就是 O(n^2)。其实在遍历过程中记录当前元素之前的最小值，那么就可以优化掉一次循环。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         if(prices.size() == 0)
  5.             return 0;
  6.         int minPrice = prices[0];
  7.         int maxGap = 0;
  8.         for(int i = 0; i < prices.size(); i++){
  9.             minPrice = min(minPrice, prices[i]);        // 更新股票最小值
  10.             maxGap = max(maxGap, prices[i] - minPrice); // 更新利润最大值
  11.         }
  12.         return maxGap;
  13.     }
  14. };

解题思路：根据题意做题即可。

  1. class Solution {
  2. public:
  3.     int strToInt(string str) {
  4.         int i = 0, flag = 1;
  5.         long res = 0; //默认flag = 1，正数
  6.         while (str[i] == ' ') i++;
  7.         if (str[i] == '-') flag = -1;
  8.         if (str[i] == '-' || str[i] == '+') i ++;
  9.         for (; i < str.size() && (str[i] >= '0' && str[i] <= '9'); i++)  {
  10.             res = res * 10 + (str[i] - '0');
  11.             if (res >= INT_MAX && flag == 1) return  INT_MAX;
  12.             if (res > INT_MAX && flag == -1) return  INT_MIN;
  13.         } 
  14.         return flag * res;
  15.     }
  16. };

解题思路：二叉搜索树，其中序遍历有序。所以，当左右子树的值都大于根的值。则移动至根的右子树。当左右子树的值都小于根的值，则移动至根的左子树。若此时，一个结点的值比根大，另一个结点的值比根小，则 这个根就是两者最近祖先结点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  13.         if(root == NULL)return NULL;
  14.         
  15.         if(p->val > root->val && q->val > root->val) 
  16.             return lowestCommonAncestor(root->right, p, q);
  17.         else if(p->val < root->val && q->val < root->val)
  18.             return lowestCommonAncestor(root->left, p, q);
  19.         else return root;
  20.     }
  21. };

解题思路：递归查询两个节点 p 和 q，如果某个节点等于节点 p 或节点 q，则返回该节点的值给父节点。如果当前节点的左右子树分别包括 p 和 q 节点，那么这个节点必然是所求的解。如果当前节点有一个子树的返回值为 p 或 q 节点，则返回该值。（告诉父节点有一个节点存在其子树中）如果当前节点的两个子树返回值都为空，则返回空指针。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  13.         if(root == NULL)return NULL;     
  14.         if(root == p||root == q)return root;
  15.  
  16.         TreeNode* left = lowestCommonAncestor(root->left, p, q);
  17.         TreeNode* right = lowestCommonAncestor(root->right, p, q);
  18.  
  19.         if(left && right)  return root;
  20.         return left ? left : right;    // 只有一个非空则返回该指针，两个都为空则返回空指针
  21.     }
  22. };

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号