問題背景

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

數據約束

• 樹中節點數目在范圍 $[2,10^5]$ 內。
• $?10^9\le Node.val\le 10^9$
• 所有 $Node.val$ 互不相同 。
• $p\le q$
• $p$ 和 $q$ 均存在于給定的二叉樹中。

解題過程

首先要想明白一種情形，如果遞歸到某個節點，發現題中所要求的兩個節點分別在這個節點的兩棵子樹中，那么它就是答案，由兩個條件保證：

• 這個節點以上（往根節點的方向）的節點，不管是不是公共祖先，都一定不滿足 最近 這個要求。
• 這個節點以下（往子樹的方向）的節點，必然不滿足同時是兩棵子樹的根節點，但是要求的兩個節點分別在兩棵子樹上。這就意味著，這些節點都不可能成為公共祖先。

在此基礎上，如果當前節點是題中要求的其中某一個節點，那么它就是答案。
剩下的情況，遇到空節點返回空是常規此操作；遞歸的過程中只在左右子樹上找到相應的節點，那就只返回遞歸相應子樹的結果；如果在子樹上都沒有找到，同樣返回空。

具體實現

/*** 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(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 root;}// 返回遞歸子樹時得到的非空的結果，兩者都為空時隨便返回哪個都可以，合并到 right 中return left != null ? left : right;}
}