C++刷剑指offer(面试题68 - I. 二叉搜索树的最近公共祖先)【递归】

糖逗

题目描述：

1. 
   
2. 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
   
3. 
   
4. 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
   
5. 
   
6. 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
   
7. 
   
8. 
   
9. 
   
10. 
    
11. 
    
12. 示例 1:
    
13. 
    
14. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    
15. 输出: 6
    
16. 解释: 节点 2 和节点 8 的最近公共祖先是 6。
    
17. 示例 2:
    
18. 
    
19. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    
20. 输出: 2
    
21. 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
    
22. 
    
23. 
    
24. 说明:
    
25. 
    
26. 所有节点的值都是唯一的。
    
27. p、q 为不同节点且均存在于给定的二叉搜索树中。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include<malloc.h>
   
5. #include <math.h>
   
6. 
   
7. using namespace std;
   
8. 
   
9. 
   
10. struct TreeNode{
    
11.         int val;
    
12.         TreeNode* left;
    
13.         TreeNode* right;
    
14.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
15.         }
    
16. };
    
17. 
    
18. 
    
19. TreeNode* CreateTree(vector<int>& input){
    
20.         TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
21.         for(int i = 0; i < input.size() ;i++){
    
22.                 tree[i].val = input[i];
    
23.                 tree[i].left = NULL;
    
24.                 tree[i].right = NULL;
    
25.                
    
26.         }
    
27.         for(int i = 0; i <= input.size()/2-1; i++){
    
28.                 if(2*i+1 <= input.size()){
    
29.                         tree[i].left = &tree[2*i+1];
    
30.                 }
    
31.                 if(2*i+2<=input.size()){
    
32.                         tree[i].right = &tree[2*i+2];
    
33.                 }
    
34.         }
    
35.         return tree;
    
36. }
    
37. 
    
38. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
39.     if(root == NULL) return;
    
40.     int insert = left + (right - left) / 2;
    
41.     res[depth][insert] = root->val;
    
42.            
    
43.     middle(root->left, res, left, insert - 1, depth + 1);
    
44.     middle(root->right, res, insert + 1, right, depth + 1);
    
45.     }
    
46. 
    
47. int treeDepth(TreeNode* root){
    
48.     if(root == NULL) return 0;
    
49.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
50.     }
    
51.       
    
52. void printTree(TreeNode* root) {
    
53.     int depth = treeDepth(root);
    
54.     int width = pow(2, depth) - 1;
    
55.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
56.     middle(root, res, 0, width - 1, 0);
    
57.     for(int i = 0; i < res.size(); i++){
    
58.                 for(int j = 0; j < res[i].size();j++){
    
59.                         if(res[i][j] == 0){
    
60.                                 cout  << " ";
    
61.                         }
    
62.                         else{
    
63.                                 cout << res[i][j];
    
64.                         }
    
65.                        
    
66.                 }
    
67.                 cout << endl;
    
68.         }
    
69.         cout << "------------------" << endl;
    
70.     }
    
71. 
    
72. 
    
73. TreeNode* findNode(TreeNode*root, int number1){
    
74.         if(root -> val == number1) return root;
    
75.         if(root -> val > number1 && root->left != NULL) return findNode(root -> left, number1);
    
76.         if(root -> val < number1 && root->right != NULL) return findNode(root -> right, number1);
    
77.         return NULL;       
    
78. }
    
79. 
    
80. 
    
81. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
82.         if((root->val-p->val)*(root->val-q->val) <= 0) return root;
    
83.         if(root -> val < p -> val) return lowestCommonAncestor(root -> right, p, q);
    
84.         if(root -> val > p -> val) return lowestCommonAncestor(root -> left, p, q);
    
85.         return NULL;
    
86.         
    
87. }
    
88. 
    
89. 
    
90. 
    
91. int main(void){
    
92.         vector<int>input;
    
93.         int number;
    
94.         cout << "please send numbers for this tree:" << endl;
    
95.         while(cin >> number){
    
96.                 input.push_back(number);
    
97.         }
    
98.         cin.clear();
    
99.         TreeNode* root = CreateTree(input);
    
100.         
     
101.         printTree(root);
     
102.         cout << "please send the first number that you want to find in this tree" << endl;
     
103.         int number1;
     
104.         cin >> number1;
     
105.         cin.clear();
     
106.         TreeNode* find_number1 = findNode(root, number1);
     
107.         printTree(find_number1);
     
108.         
     
109.         cout << "please send the second number that you want to find in this tree" << endl;
     
110.         int number2;
     
111.         cin >> number2;
     
112.         TreeNode* find_number2 = findNode(root, number2);
     
113.         printTree(find_number2);
     
114.         
     
115.         TreeNode* res =  lowestCommonAncestor(root, find_number1, find_number2);
     
116.         printTree(res);
     
117. 
     
118.         return 0;
     
119. }

复制代码

注意事项：
1.这里的代码包括输入vector转化为二叉树、将二叉树打印、寻找二叉树中等于目标值的根节点树、返回两个树之间公共根节点的完整树。
2.这里的输入必须保证根节点介于左右两个节点之间：左节点值<根节点值<右节点值 例如[4,2,8,1,3,7,9]可以，[1,2,3,4,5,6,7]不可以。

糖逗

这里的代码部分用到了之前主题中的代码：https://fishc.com.cn/thread-163150-1-1.html

糖逗

1. TreeNode* findNode(TreeNode*root, int number1){
   
2.         if(root -> val == number1) return root;
   
3.         if(root -> val > number1 && root->left != NULL) return findNode(root -> left, number1);
   
4.         if(root -> val < number1 && root->right != NULL) return findNode(root -> right, number1);
   
5.         return NULL;      
   
6. }
   
7. 
   
8. 
   
9. 
   
10. 
    
11. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
12.         if((root->val-p->val)*(root->val-q->val) <= 0) return root;
    
13.         if(root -> val < p -> val) return lowestCommonAncestor(root -> right, p, q);
    
14.         if(root -> val > p -> val) return lowestCommonAncestor(root -> left, p, q);
    
15.         return NULL;
    
16.         
    
17. }

复制代码

以上两段代码是解本问题的新增代码。分别用于查找树中根节点等于目标值的子树和返回两个数的最近公共根节点。

糖逗