給出一個二叉樹咬荷，輸入兩個樹節(jié)點路呜，求它們的最低公共祖先迷捧。
一個樹節(jié)點的祖先節(jié)點包括它本身。
注意：
輸入的二叉樹不為空胀葱；
輸入的兩個節(jié)點一定不為空党涕，且是二叉樹中的節(jié)點；
樣例
二叉樹[8, 12, 2, null, null, 6, 4, null, null, null, null]如下圖所示：
8
/ \q
12 2
/ \
6 4
1. 如果輸入的樹節(jié)點為2和12巡社，則輸出的最低公共祖先為樹節(jié)點8膛堤。
2. 如果輸入的樹節(jié)點為2和6，則輸出的最低公共祖先為樹節(jié)點2晌该。
分析：
算法一：遞歸
若 rootrootroot 是 p,q 的 最近公共祖先 肥荔，則只可能為以下情況之一：
- p 和 q在 root 的子樹中绿渣，且分列 root的 異側(cè)（即分別在左、右子樹中）燕耿；
- p=root 中符，且 q 在 root 的左或右子樹中；
- q=root 誉帅，且 p 在 root 的左或右子樹中淀散；
遞歸解析：
終止條件：
當越過葉節(jié)點，則直接返回 null蚜锨；
當 root 等于 p,q 档插，則直接返回 root ；遞推過程：
遞歸左子節(jié)點亚再，返回值記為 left 郭膛；
遞歸右子節(jié)點，返回值記為 right 氛悬；返回值： 根據(jù) left 和 right 则剃，可展開為四種情況；
當 left 和 right同時為空 ：說明 root的左 / 右子樹中都不包含 p,q 如捅，返回 null 棍现；
當 left 和 right 同時不為空 ：說明 p,q 分列在 root 的 異側(cè) （分別在 左 / 右子樹），因此 root 為最近公共祖先镜遣，返回 root 轴咱；
當 left 為空 ，right 不為空 ：p,q 都不在 root 的左子樹中烈涮，直接返回 right 。具體可分為兩種情況：
p,q 其中一個在 root的 右子樹 中窖剑，此時 right 指向 p（假設(shè)為 p ）坚洽；
p,q 兩節(jié)點都在 roo 的 右子樹 中，此時的 right 指向 最近公共祖先節(jié)點 西土；
當 left不為空 讶舰， right 為空 ：同理；
/**
* 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 || root==p || root==q) return root;//遞歸終止條件
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;//兩個節(jié)點分別位于左子樹和右子樹
if(!left) return right;//左子樹中兩個節(jié)點都找不到
return left;//右子樹中兩個節(jié)點都找不到
}
};
復(fù)雜度分析
時間復(fù)雜度：O(N)需了，其中 NNN 是二叉樹的節(jié)點數(shù)跳昼。二叉樹的所有節(jié)點有且只會被訪問一次，因此時間復(fù)雜度為 O(N)肋乍。
空間復(fù)雜度：O(N) 鹅颊，其中 NNN 是二叉樹的節(jié)點數(shù)。遞歸調(diào)用的棧深度取決于二叉樹的高度墓造，二叉樹最壞情況下為一條鏈堪伍，此時高度為 NNN锚烦，因此空間復(fù)雜度為 O(N)。
算法二：存儲父節(jié)點
我們可以用哈希表存儲所有節(jié)點的父節(jié)點帝雇，然后我們就可以利用節(jié)點的父節(jié)點信息從 p 結(jié)點開始不斷往上跳涮俄，并記錄已經(jīng)訪問過的節(jié)點，再從 q 節(jié)點開始不斷往上跳尸闸，如果碰到已經(jīng)訪問過的節(jié)點彻亲，那么這個節(jié)點就是我們要找的最近公共祖先。
從根節(jié)點開始遍歷整棵二叉樹吮廉，用哈希表記錄每個節(jié)點的父節(jié)點指針苞尝。
從 p 節(jié)點開始不斷往它的祖先移動，并用數(shù)據(jù)結(jié)構(gòu)記錄已經(jīng)訪問過的祖先節(jié)點茧痕。
同樣吼拥，我們再從 q 節(jié)點開始不斷往它的祖先移動优训，如果有祖先已經(jīng)被訪問過，即意味著這是 p 和 q 的深度最深的公共祖先。
復(fù)雜度分析
時間復(fù)雜度：O(N)檀蹋，其中 N 是二叉樹的節(jié)點數(shù)。二叉樹的所有節(jié)點有且只會被訪問一次轻专，從 p 和 q 節(jié)點往上跳經(jīng)過的祖先節(jié)點個數(shù)不會超過 N蚓峦，因此總的時間復(fù)雜度為 O(N)。
空間復(fù)雜度：O(N)气破，其中 N 是二叉樹的節(jié)點數(shù)聊浅。遞歸調(diào)用的棧深度取決于二叉樹的高度，二叉樹最壞情況下為一條鏈现使，此時高度為 N低匙，因此空間復(fù)雜度為 O(N)，哈希表存儲每個節(jié)點的父節(jié)點也需要 O(N)的空間復(fù)雜度碳锈，因此最后總的空間復(fù)雜度為 O(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:
unordered_map<TreeNode*, TreeNode*> father;
unordered_map<TreeNode*, bool> vis;
void dfs(TreeNode* root) {
if(root->left) father[root->left] = root, dfs(root->left);
if(root->right) father[root->right] = root, dfs(root->right);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
father[root] = nullptr;
dfs(root);
while(p) vis[p] = true, p = father[p];
while(q) {
if(vis[q]) return q;
q = father[q];
}
return nullptr;
}
};
