题目描述
给出一个二叉树,输入两个树节点,求它们的最低公共祖先。
一个树节点的祖先节点包括它本身。
注意:
输入的二叉树不为空;
输入的两个节点一定不为空,且是二叉树中的节点;
样例
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示:
8
/ \
12 2
/ \
6 4
-
如果输入的树节点为2和12,则输出的最低公共祖先为树节点8。
-
如果输入的树节点为2和6,则输出的最低公共祖先为树节点2。
样例
分别找出根节点到两个节点的路径,则最后一个公共节点就是最低公共祖先了。
const int N = 1e5+10;
TreeNode* stk[N], *q1[N], *q2[N];
int t1=0, t2 = 0;
class Solution {
public:
void dfs(TreeNode * root){
auto p = root;
TreeNode* pre;
while(p||t1){
if(p){
stk[++t1] = p;
p = p->left;
}else{
p = stk[t1];
if(!p->right||p->right==pre){
t1--;
cout << p->val<<"*";
pre = p;
p = nullptr;
}else{
p = p->right;
}
}
}
}
int find(TreeNode * root, TreeNode* q, TreeNode* stk[]){
t1 = 0;
auto p = root;
TreeNode* pre;
while(p||t1){
if(p){
stk[++t1] = p;
p = p->left;
}else{
p = stk[t1];
if(!p->right||p->right==pre){
if(p==q) return t1;
t1--;
pre = p;
p = nullptr;
}else{
p = p->right;
}
}
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* res;
int t1 = find(root, p, q1);
int t2 = find(root, q, q2);
int i;
for(i= 1; i<=t1&i<=t2; i++){
if(q1[i]!=q2[i]) return q1[i-1];
}
return q1[i-1];
}
};