迪奥官网网站做的好吗/上海网站优化公司

题目：     

     给定一颗二叉树，以及其中的两个node（地址均非空），要求给出这两个node的一个公共父节点，使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度，并实现具体函数，函数输入输出请参考如下的函数原型：

strucy TreeNode{TreeNode* left;   //指向左子树TreeNode* right;   //指向右子树TreeNode* father;   //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}

方法1：

     算法复杂度为O(n)。

     先查找高度。然后类似于查找两条链表第一个公共节点的方法进行遍历比较：

int getHeight(TreeNode *node) {int height = 0;while (node) {height++;node = node->parent;}return height;
}TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {int height1 = 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;}return first;
}

方法2：

    使用辅助存储空间。两个栈依次压入从该节点到根节点的指针。依次弹出栈比较节点。。

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){if(!first||!second)return;if(first==second)return first;stack<node> s1;stack<node> s2;node t1,t2;while(!first){s1.push(first);first=first->father;}while(!second){s2.push(second);first=first->father;}while(!s1.empty()&&!s2.empty()){t1=s1.top();s1.pop();t2=s2.top();s2.pop();if(t1!=t2)return NULL;else if((t1==t2)&&!s1.empty()&&!s2.empty()&&(s1.top()!=s2.top()))//当前节点相等，下一级不相等return t1;else if((t1==t2)&&(s1.empty()||s2.empty()))//当前节点相等，下一级为空return t1;}	return NULL;
}

引申：

      考虑特殊情况，即二叉树为二叉查找数的情况：

TreeNode* LowestCommonAncestor(TreeNode* head,TreeNode* first,TreeNode* second){if(!first||!second)return;if(first==second)return first;if(first->value>second->value){TreeNode* t;t=first;first=second;second=first;}if(first->value>head->value)return LowestCommonAncestor(head->right,first,second);else if(second->value<head->value)return LowestCommonAncestor(head->left,first,second);elsereturn head;
}