题目描述：
测试用例：
思路：
基本流程：
-
递归结束条件：
-
传入参数root为null，返回root
-
传入参数root为p或q节点，返回root
-
递归左右子树，获得递归结果left，right
-
递归结果的四种情况：
-
左右子树都不为null，返回根root就是最近公共祖先
-
左子树为null，返回右子树，由于左子树都不包含p或q一定不为公共祖先，右子树可能为公共祖先或p或q或null
-
同理：右子树为null，返回左子树。
-
补充：情况2和情况3包含了三种情况：
-
左子树为null，右子树不为null
-
右子树为null，左子树不为null
-
左右子树都为null
代码：
import java.util.Objects;
public class P236LowestCommonAncestorOfABinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
//root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
public static void main(String[] args) {
Solution solution = new P236LowestCommonAncestorOfABinaryTree().new Solution();
// TO TEST
TreeNode root = new TreeNode(3);
TreeNode root1 = new TreeNode(5);
TreeNode root2 = new TreeNode(1);
TreeNode root3 = new TreeNode(6);
TreeNode root4 = new TreeNode(2);
TreeNode root5 = new TreeNode(0);
TreeNode root6 = new TreeNode(8);
TreeNode root7 = new TreeNode(7);
TreeNode root8 = new TreeNode(4);
root.left = root1;
root.right = root2;
root1.left = root3;
root1.right = root4;
root2.left = root5;
root2.right = root6;
root4.left = root7;
root4.right = root8;
root3.left = root3.right = root5.left = root5.right = root6.left = root6.right = root7.left = root7.right = root8.left = root8.right = null;
System.out.println(solution.lowestCommonAncestor(root, root1, root2).val);
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (Objects.isNull(root) || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (Objects.nonNull(left) && Objects.nonNull(right)) return root;
else if (Objects.isNull(left)) return right;
else return left;
}
}
}