LCR 194. 二叉樹的最近公共祖先

LCR 193. 二叉搜索樹的最近公共祖先 也是一樣的做法

二叉樹的公共祖先的定義：對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）

分類討論：

1. 當前節點為空 or 當前節點等于p or 當前節點等于q，返回當前節點
2. 左右子樹相等，返回當前節點
3. 左子樹為空，右子樹不為空，返回右子樹，反之左子樹，都為空，就返回空即可

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }
        TreeNode lnode = lowestCommonAncestor(root.left, p, q);
        TreeNode rnode = lowestCommonAncestor(root.right, p, q);
        if(lnode != null && rnode != null) {
            return root;
        }
        return lnode != null ? lnode : rnode;
}