236. 二叉树的最近公共先人

【题目】：236. 二叉树的最近公共先人
终止条件：

• 当root到叶节点终止
  
• 当root是p或q终止（由于要求的是公共先人，如果遍历到p，就算q还在p的下边，他们的公共先人还是p）
  

   这也说明白：如果返回的是nullptr，说明p、q不在这棵树中
  返回情况：

• left == nullptr && right == nullptr：说明root的左右子树都没有p、q，直接返回nullptr
  
• left != nullptr && right == nullptr：说明p、q在root的左子树中，那么只需要返回left（由于前面只要碰到p或q就会终止，以是此时left就是p、q中相对上边的节点）
  
• right != nullptr && left == nullptr：说明p、q在root的右子树中，那么只要返回right即可（原因同上）
  
• right != nullptr && left != nullptr：说明p、q分散在root的左右子树中，此时root就是他们的最近公共先人节点
  

1. class Solution {
2. public:
3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
4.         // 如果root是p 或 q 或 nullptr，就不需要再往下遍历了
5.         if(root == nullptr || root == p || root == q) {
6.             return root;
7.         }
8.         // 如果root不是p 或 q，就继续遍历root的左右子树
9.         TreeNode* left = lowestCommonAncestor(root->left, p, q);
10.         TreeNode* right = lowestCommonAncestor(root->right, p, q);
11.         
12.         if(left == nullptr && right == nullptr) {// 如果p 和 q都没找到，更不可能有公共祖先了
13.             return nullptr;
14.         }else if(left == nullptr) {// 如果左子树没有p也没有q，那就返回右子树
15.             return right;
16.         }else if(right == nullptr) {// 如果右子树没有p也没有q，那就返回左子树
17.             return left;
18.         }else {// 如果p和q分别在左右子树中，那就返回root
19.             return root;
20.         }
21.     }
22. };

复制代码

• 时间复杂度: O(n)
  
• 空间复杂度: O(n)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。