236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)
/**
* 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) {
/**后序遍历
* 终止条件:如果root==null||root==p||root==q直接返回root
* 对左右子树进行查找，根据左右子树的返回值进行判断：
* 1：如果左右子树返回的均为null,p和q都不在当前树中，返回null
* 2：如果左右子树的返回值都不为null,由于值唯一，左右子树的返回值就是p,q。此时root为LCA(二叉树的最近公共祖先)
* 3：如果左右子树返回值只有一个不为null, 说明p,q在同一root子树中, 最先找到的那个节点为LCA
* **/
if(root==null||root==p||root==q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left==null&&right==null) return null;
else if(left!=null&&right!=null) return root;
else return left==null?right:left;
}
}
