力扣--二叉树的最近公共祖先

思路：

1. 首先，我们采用后根遍历【这种遍历方式非常适合这个问题，因为我们要找的是最深的（即离根最远的）公共祖先，所以我们应该从底部向上工作，先找到子树中的最近公共祖先，再逐步返回到更高的层次。】
2. 其次，我们理清思路，大致分为三种情况：①两个节点在根节点的两侧，那么应该返回根节点。② p 为根节点，返回 p。③ q 为根节点，返回 q。
3. 根据后根遍历的思想，首先采用dfs获取左子树中的最近公共祖先left，右子树的最近公共祖先right，然后来判断以下四种情况：①left和right都为空，那么说明没有找到最近公共祖先，返回空。②left为空，right不为空，说明p和q都在根节点的一侧，返回right即可。③同理，left不为空，right为空，返回left即可。④left和right都不为空，说明p和q在根节点的两侧，返回根节点即可。

代码:

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr ||root==p||root==q){return root;}
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left==nullptr && right==nullptr){return nullptr;}
        else if(left==nullptr){return right;}
        else if(right==nullptr){return left;}
        else{return root;}
    }
};

Python：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root==None or root==p or root==q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left==None and right==None:
            return None
        elif left==None:
            return right
        elif right==None:
            return left
        else:
            return root