给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数原型:
C++函数原型:
strucy TreeNode{
TreeNode* left; //指向左子树
TreeNode* right; //指向右子树
TreeNode* father; //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}
思路一:我们首先找到两个节点的高度差,然后从较靠近根结点的一层开始向上找,若父节点为同一节点则该节点为解。
intgetHeight(TreeNode *node) {
intheight = 0;
while(node) {
height++;
node = node->parent;
}
returnheight;
}
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
intheight1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
if(diff < 0) {
diff = -diff;
while(diff--) {
second = second->parent;
}
} else{
while(diff--) {
first = first->parent;
}
}
while(first != second) {
first = first->parent;
second = second->parent;
}
returnfirst;
}
思路二:若允许浪费空间,那么可以用两个Stack来存储从first和second到根结点的各个节点,然后出栈时比较地址是否一致,最后一个地址一致的节点为解。
两种方法最坏时间复杂度均为O(n)。