/**
* 基础版
* 给定p，q都是在树中
* 有两种情况：
* 1. p和q分布在LCA的两侧
* 2. p和q在同一侧（p是q的祖先 或者是 q是p的祖先）
* 先考虑第一种情况，例如：
* 1
* / \
* 2 4
* 2和4的LCA是1，向下递归返回时，2返回2，4返回4，1接受到的left和right的返回值都存在值，那么就返回自己
* 也就是说=> 只要找到目标节点，就往上返回该节点
* ---------------------------------
* 第二种情况，例如：
* 1
* /
* 2
* \
* 3
* 2和3的LCA是2，2接收到的是3，而自己也是目标节点，那么就返回自己
* --------------注意1----------------
* 不用考虑在1处，只有一个返回值，如何判断是否有效。因为：两个节点必定在树中，如果root接收到一个值，那么就表示root之下就有p和q的LCA
* 如果接收到两个值，那么自己就是LCA
* --------------注意2----------------
* Corner case: p就是root 或者 q就是root
*/
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// base case:
// 如果当前结点(root)是p或者是q，就返回自己
if (root == null || root == p || root == q) {
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
if (leftNode != null && rightNode != null) { // 接收到两个值，返回root
return root;
} else if (leftNode != null && rightNode == null) { // 接收到一个值，就返回该node
return leftNode;
} else {
return rightNode;
}
}