C++刷LeetCode（面试题 04.08. 首个共同祖先）【递归】

糖逗

题目描述：

1. 设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
   
2. 
   
3. 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
   
4. 
   
5.     3
   
6.    / \
   
7.   5   1
   
8. / \ / \
   
9. 6  2 0  8
   
10.   / \
    
11. 7   4
    
12. 示例 1:
    
13. 
    
14. 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    
15. 输出: 3
    
16. 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
    
17. 示例 2:
    
18. 
    
19. 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    
20. 输出: 5
    
21. 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
    
22. 说明:
    
23. 
    
24. 所有节点的值都是唯一的。
    
25. p、q 为不同节点且均存在于给定的二叉树中。
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/first-common-ancestor-lcci
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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.         //递归
    
14.         if(root == NULL || root == p || root == q)return root;
    
15.         TreeNode* left = lowestCommonAncestor(root -> left, p, q);
    
16.         TreeNode* right = lowestCommonAncestor(root -> right, p, q);
    
17.         if(left != NULL && right != NULL)return root;
    
18.         else if(left == NULL)return right;
    
19.         return left;
    
20.     }
    
21. };

复制代码