236. 二叉树的最近公共祖先(中等）-二叉树

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

分析

• 递归关键想好两点，第一点这个函数的作用，输入和输出
• 第二点就是终止条件
• 二叉树的递归，分成三种遍历方式，先序，中序和后序，其实就是你要巡逻的地方，每个都能走一遍，走的过程中，你需要做的一些计算等等

# 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 not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not left:
            return right
        
        if not right:
            return left
        
        return root