labuladong Git原理之最近公共祖先
遇到任何递归类型的问题，无非就是“灵魂三问”
- 这个函数是干什么的？(不要跳进递归，没用。)
- 这个函数参数中的变量是什么？
- 得到函数的递归结果，你应该干什么
明确递归函数的含义：递归函数返回（以root为基础的）两个
p,q节点的最近公共祖先- 递归函数说：你不要跳进递归，你要相信我能返回你需要的东西（也就是最近公共祖先）；如果我能找到其中一个p（或q），我就返回这个p（或q）；如果都找不到，我就返回NULL
- 比如：p为7，q为8，此时的root为2。你要相信我能返回公共祖先4（你不用管我是怎么知道公共祖先是4的，你相信我就行）
- 比如：p为7，q为6，此时的root为2。我返回7
- 比如：p为7，q为8，此时的root为6。我只能返回NULL
- 递归函数说：你不要跳进递归，你要相信我能返回你需要的东西（也就是最近公共祖先）；如果我能找到其中一个p（或q），我就返回这个p（或q）；如果都找不到，我就返回NULL
递归结束的条件（或者base case）：如果root为空，返回NULL；如果root本身就是p（或q），则返回p（或q）
处理递归函数返回的结果（相当于后序遍历）:先求root.left的结果（左），再求root.right的结果（右）。然后根据结果来操作当前的root状态（中）
- 如果左右的结果都是NULL，说明p和q都不在以root为根的树中，则返回NULL
- 如果左右的结果都不是NULL，说明p和q在root的左右子树中各有一个，则返回当前的root
- 比如：p为7，q为5，此时的root为2。2的左子树返回7，右子树返回5。此时的最近公共祖先就是当前的root：2
- 如果左结果为NULL，右结果不是NULL，说明p和q都在右子树中，此时返回右结果（如果右结果为NULL，左结果不是NULL，说明p和q都在左子树中，此时返回左结果）
- 比如：p为7，q为5，此时的root为1。root的左子树返回2，右子树返回NULL。则此时1对应的结果就是
非NULL的那个子树的结果
- 比如：p为7，q为5，此时的root为1。root的左子树返回2，右子树返回NULL。则此时1对应的结果就是
# # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# base case 或者递归出口
if not root:return None
if root==p or root==q:return root
# 后序遍历：左
l=self.lowestCommonAncestor(root.left,p,q)
# 后序遍历：右
r=self.lowestCommonAncestor(root.right,p,q)
# 后序遍历：中
# 都为空，没找到
if not l and not r:return None
# 都不为空，左右子树各有一个p q，返回当前root
if l and r:return root
# 一个为空，一个不为空, 返回不为空的结果
return l if l else r//// * 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){return nullptr;}
if (root==p || root==q){return root;}
// 后序遍历：左右
TreeNode* l= lowestCommonAncestor(root->left,p,q);
TreeNode* r= lowestCommonAncestor(root->right,p,q);
// 后序遍历：中
if (l==nullptr && r== nullptr){return nullptr;} //都为空，返回空
if (l and r){return root;} // 都不为空，返回当前的root
return l?l:r; // 有一个为空，一个不为空，返回不为空的
}
};
