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
?????????*?對(duì)左右子樹進(jìn)行查找球昨，根據(jù)左右子樹的返回值進(jìn)行判斷：
?????????*?1：如果左右子樹返回的均為null,p和q都不在當(dāng)前樹中逛尚，返回null
?????????*?2：如果左右子樹的返回值都不為null,由于值唯一晒奕，左右子樹的返回值就是p,q。此時(shí)root為L(zhǎng)CA(二叉樹的最近公共祖先)
?????????*?3：如果左右子樹返回值只有一個(gè)不為null,?說(shuō)明p,q在同一root子樹中,?最先找到的那個(gè)節(jié)點(diǎn)為L(zhǎng)CA
?????????*?**/
????????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;
????}
}
