題目鏈接
tag:

• Medium枣抱；

question
??Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes' values will be unique.
• p and q are different and both values will exist in the binary tree.

思路：
??這道求二叉樹(shù)的最小共同父節(jié)點(diǎn)，我們可以用遞歸來(lái)實(shí)現(xiàn)茬高，在遞歸函數(shù)中，我們首先看當(dāng)前結(jié)點(diǎn)是否為空，若為空則直接返回空赞咙，若為p或q中的任意一個(gè)，也直接返回當(dāng)前結(jié)點(diǎn)把跨。否則的話(huà)就對(duì)其左右子結(jié)點(diǎn)分別調(diào)用遞歸函數(shù)人弓，由于這道題限制了p和q一定都在二叉樹(shù)中存在，那么如果當(dāng)前結(jié)點(diǎn)不等于p或q着逐，p和q要么分別位于左右子樹(shù)中崔赌，要么同時(shí)位于左子樹(shù)，或者同時(shí)位于右子樹(shù)耸别，那么我們分別來(lái)討論：

??若p和q分別位于左右子樹(shù)中健芭，那么對(duì)左右子結(jié)點(diǎn)調(diào)用遞歸函數(shù)，會(huì)分別返回p和q結(jié)點(diǎn)的位置秀姐，而當(dāng)前結(jié)點(diǎn)正好就是p和q的最小共同父結(jié)點(diǎn)慈迈，直接返回當(dāng)前結(jié)點(diǎn)即可，這就是題目中的例子1的情況省有。

??若p和q同時(shí)位于左子樹(shù)痒留，這里有兩種情況，一種情況是left會(huì)返回p和q中較高的那個(gè)位置蠢沿，而right會(huì)返回空伸头，所以我們最終返回非空的left即可，這就是題目中的例子2的情況舷蟀。還有一種情況是會(huì)返回p和q的最小父結(jié)點(diǎn)恤磷，就是說(shuō)當(dāng)前結(jié)點(diǎn)的左子樹(shù)中的某個(gè)結(jié)點(diǎn)才是p和q的最小父結(jié)點(diǎn)面哼，會(huì)被返回。

??若p和q同時(shí)位于右子樹(shù)扫步，同樣這里有兩種情況魔策，一種情況是right會(huì)返回p和q中較高的那個(gè)位置，而left會(huì)返回空河胎，所以我們最終返回非空的right即可闯袒，還有一種情況是會(huì)返回p和q的最小父結(jié)點(diǎn)，就是說(shuō)當(dāng)前結(jié)點(diǎn)的右子樹(shù)中的某個(gè)結(jié)點(diǎn)才是p和q的最小父結(jié)點(diǎn)游岳，會(huì)被返回搁吓，寫(xiě)法很簡(jiǎn)潔，代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root || p == root || q == root) 
           return root;
       TreeNode *left = lowestCommonAncestor(root->left, p, q);
       TreeNode *right = lowestCommonAncestor(root->right, p , q);
       if (left && right) 
           return root;
       return left ? left : right;
    }
};