68 - II. 二叉树的最近公共祖先.md

解题思路

后序遍历

需要先找到 p、q 节点，再判断父节点，所以需要自底向上后序遍历

left 和 right 返回值可能四种情况：

1. 都为空，说明谁也没找到，向上继续返回 null
2. 都不为空，说明既找到了 p，也找到了 q，当前节点就是公共祖先
3. 一个为空，另一个不为空，不为空的可能找到了最近公共祖先，也可能只是找到了某个节点

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right, p, q)
    if l == nil {
        return r
    }
    if r == nil {
        return l
    }
    return root
}