題目鏈接：
題目描述：
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先珠插。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p掀宋、q事镣，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）∷ⅲ”
例如，給定如下二叉樹(shù): root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點(diǎn)5和節(jié)點(diǎn)1的最近公共祖先是節(jié)點(diǎn)3琐驴。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn)5和節(jié)點(diǎn)4的最近公共祖先是節(jié)點(diǎn)5俘种。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
說(shuō)明:
- 所有節(jié)點(diǎn)的值都是唯一的绝淡。
- p宙刘、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹(shù)中。
算法：
此題比235.二叉搜索樹(shù)的最近公共祖先更難牢酵。對(duì)于二叉搜索樹(shù)而言悬包，樹(shù)的結(jié)點(diǎn)本身有序，只需要搜索到的節(jié)點(diǎn)的值進(jìn)行比較馍乙，很容易就得到了最近公共祖先布近，但是此題是對(duì)任意二叉樹(shù)進(jìn)行操作垫释，難度顯然更大。
首先吊输，對(duì)于二叉樹(shù)的搜索饶号，我們通常使用的是遞歸操作铁追。遞歸操作講究的是分而化之季蚂。基本的思路都是：
TreeNode* fun(TreeNode* root) {
if (root == NULL)
return NULL;
if (root 滿足條件)
return root;
...
其他操作
...
TreeNode* left = fun(root->left);
TreeNode* right = fun(root->right);
...
其他操作
...
return result;
}
我們把模型化為一個(gè)根節(jié)點(diǎn)琅束，與左子樹(shù)和右子樹(shù)扭屁。考慮根節(jié)點(diǎn)涩禀，如果根節(jié)點(diǎn)為公共祖先料滥，需要滿足什么情況?
- 根節(jié)點(diǎn)為p或者q
- 根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)分別找到p和q。
顯然我們的偽代碼為：
if (root == p || root == q)
return root;
if (root->left 存在p或q && root->right 存在p或q)
return root;
再考慮左右子樹(shù)艾船，顯然葵腹，我們對(duì)左右子樹(shù)調(diào)用函數(shù)本身，返回的一定是q或p或公共祖先屿岂。那么践宴，如果左右兩邊都返回結(jié)果，就一定是p和q爷怀，則root為公共祖先阻肩；如果有一邊為NULL，則表示另一邊一定是公共祖先运授。題目已解烤惊。
代碼：
/**
* 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 == NULL)
return root;
// 一個(gè)節(jié)點(diǎn)也可以是它自己的祖先
if (root == p || root == q)
return root;
// 調(diào)用函數(shù)本身，有可能返回p, q, NULL
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 都不等于NULL吁朦，說(shuō)明p柒室，q在左右兩邊。否則left或者right即為公共節(jié)點(diǎn)
if (left != NULL && right != NULL)
return root;
else if (left != NULL)
return left;
else
return right;
}
};
