最近公共祖先
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。注意事项
假设给出的两个节点都在树中存在
样例
对于下面这棵二叉树
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7标签
LintCode 版权所有 领英 二叉树 脸书
code
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// write your code here
TreeNode * ancestor = NULL;
if(root==NULL || A==NULL || B==NULL)
return ancestor;
vector<TreeNode *> pathA, pathB;
searchTree(root, A, pathA);
searchTree(root, B, pathB);
int sizeA=pathA.size(), sizeB=pathB.size();
int size = sizeA>sizeB ? sizeB : sizeA, i=0;
bool find = false;
for(i=0; i<size; i++) {
if(pathA[i] != pathB[i]) {
find = true;
return ancestor;
}
else
ancestor = pathA[i];
}
if(find == false)
ancestor = pathA[size-1];
return ancestor;
}
bool searchTree(TreeNode *root, TreeNode *node, vector<TreeNode *> &path) {
if(root==NULL || node==NULL) {
return false;
}
path.push_back(root);
// 找到了
if(root->val == node->val) {
return true;
}
if(root->left != NULL) {
if(searchTree(root->left, node, path)) {
return true;
}
}
if(root->right != NULL) {
if(searchTree(root->right, node, path)) {
return true;
}
}
//回溯
path.pop_back();
return false;
}
};