76.二叉树的最近公共祖先

题目

思路

代码

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 and not right: 
        	return # 1.
        if not left: 
        	return right # 3.
        if not right: 
        	return left # 4.
        return root # 2. if left and right: