给定一颗二叉树，以及其中的两个node（地址均非空），要求给

/*问题描述：
写一个函数，输入一棵二叉树，树中每个结点存放了一个整数值，
函数返回这棵树中相差最大的两个结点间的差的绝对值。
解决思路：
定义两个参数n_max和n_min,遍历二叉树将结点元素的值与n_max和n_min比较并更新,最后返回n_max-n_min。*/
#include <iostream> 
#include <limits.h> 
#include <math.h> 
using namespace std;  
struct Node  
{  
    int val;  
    Node *left;  
    Node *right;  
    Node(int x) : val(x), left(NULL), right(NULL) {}  
};  
int maxValue(Node* root)  
{  
    if (root == NULL)  
        return 0;  
    int left = maxValue(root->left);  
    int right = maxValue(root->right);  
    int max = left>right ? left:right;  
    return root->val> max ? root->val : max;  
}  
int minValue(Node* root)  
{  
    if (root == NULL)  
        return 32767;  
    int left = minValue(root->left);  
    int right = minValue(root->right);  
    int min = left<right ? left:right;  
    return root->val < min ? root->val : min;  
}  
int diff(Node* root)  
{  
    return maxValue(root) - minValue(root);  
}
int main()  
{  
    Node* root0 = new Node(2);  
    Node* left01 = new Node(-5);  
    Node* right02 = new Node(-3);   
    Node* left11 = new Node(6);  
    Node* right12 = new Node(-2); 
    Node* left21 = new Node(-7);  
    Node* right22 = new Node(3);
    root0->left = left01;  
    root0->right = right02;
    left01->left =left11;
    left01->right=right12;
    right02->left=left21;
    right02->right=right22;
    cout << diff(root0) << endl;  
    return 0;  
}  

int nodeHeight(TreeNode* node)
{
    int height = 0;
    while(node != NULL)
    {
        height++;
        node = node->father;
    }
}
TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second)
{
    int diff = nodeHeight(first) - nodeHeight(second);
    if(diff > 0)
    {
        while(diff > 0)
        {
            first = first->father;
            diff--;
        }
    }
    else
    {
        while(diff < 0)
        {
            second = second->father;
            diff++;
        }
    }
    while(first != second)
    {
        first = first->father;
        second = second->father;
    }
    return first;
}

class TreeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.father=None
def getheight(TreeNode):
    height=0
    while TreeNode:
        height+=1
        TreeNode=TreeNode.father
    return height
def lowestcommonancestor(TreeNode1,TreeNode2):
    height1=getheight(TreeNode1)
    height2=getheight(TreeNode2)
    if height1>height2:
        diff = height1 - height2
        while diff:
            TreeNode1 = TreeNode1.father
            diff -= 1
    else:
        diff = height2 - height1
        while diff:
            TreeNode2 = TreeNode2.father
            diff -= 1
    while TreeNode1!=TreeNode2:
        TreeNode1 = TreeNode1.father
        TreeNode2 = TreeNode2.father
    return TreeNode1
最坏时间复杂度为O(n)

public class FindFatherNode {
    public TreeNode findFather(TreeNode first,TreeNode second){
         int len1 = 0;
         int len2 = 0;
         TreeNode temp1 = first;
         TreeNode temp2 = second;
         while(temp1!=null){
             temp1 = temp1.father;
             len1++;
             
         }
         while(temp2!=null){
             temp2 = temp2.father;
             len2++;
             
         }
         int m = len1>len2?len2:len1;
         for(int i = 1;i<=m;i++){
             temp1 = first.father;
         }
         return temp1;
    }

}

	strucy TreeNode{



	     TreeNode* left;   //指向左子树



	     TreeNode* right;   //指向右子树



	     TreeNode* father;   //指向父亲节点



	};



	TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){



	  set<TreeNode*> path;



	  while (first->father){



	   path.insert(first->father);



	   first = first->father;



	  }



	  while (second->father){



	    if (path.find(second->father){



	       return second->father;



	    }



	  }



	  return NULL;



	}

struct TreeNode{
     TreeNode* left;   //指向左子树
     TreeNode* right;   //指向右子树
     TreeNode* father;   //指向父亲节点
};
//将各自的父节点都放在栈里面，找到第一个不相同的结点。上一个结点即为所求
//特殊情况：1.根节点为最近公共结点（处于根节点的左右两侧）
//2.最近公共父节点为first与second两者之一
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
    stack<TreeNode*>stk1;
    stack<TreeNode*>stk2;
    while (first!= NULL) {
       stk1.push(first->father);
       first = first->father;
    }
     while (second!= NULL) {
       stk1.push(second->father);
       second= second->father;
    }
    int length = stk1.size() < stk2.size() ? stk1.size() : stk2.size();
    TreeNode* pResult = NULL;
    for (int i = 0; i < length; ++i) {
       TreeNode* pNode1 = stk1.top();
       TreeNode* pNode2 = stk2.top();
       if (pNode1 == pNode2) {
           stk1.pop();
           stk2.pop();
           pResult = pNode1;
        }
       else {
          return pResult;
    }
    return pResult;
   } 
}

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.right = self.left = self.father = None

def lowesetCommaonAncestor(node1, node2):
    if not node1 or not node2:
        return None

    if node1 == node2:
        return node1

    if hasSubNode(node1, node2):
        return node1

    return lowesetCommaonAncestor(node1.father, node2)

def hasSubNode(root, child):
    if not root or not child:
        return False
    if root == child:
        return True

    return hasSubNode(root, child.parent)

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second)
{
	if(first == NULL||second == NULL)
		return NULL;
	if(first == second)
	{
		return first;
	}
	if(first == second.father)
			return first;
	if(second == first.father)
			return second;
	TreeNode *tempFirst = first;
	TreeNode *tempSecond = second;

	while(tempFirst->father != NULL&&tempSecond->father!=NULL)
	{
		tempFirst = tempFirst->father;
		tempSecond = second;
		while(tempSecond->father != NULL)
		{
			if(tempSecond == tempFirst)
			{
				return tempFirst;
			}
			tempSecond = tempSecond->father;
		}		
	}
}

TreeNode * LowestCommonAncestor(TreeNode *first, TreeNode *second)

用递归遍历first的父节点的另一个子数中是否存在second节点，不过就是时间复杂度有点高
bool Compare(TreeNode* tempNode, TreeNode* second)
{
	if (tempNode == second)
	{
		return true;
	}

	if (tempNode->left)
	{
		Compare(tempNode->left, second);
	}
	if (tempNode->right)
	{
		Compare(tempNode->right, second);
	}
}

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second)
{
	if (first == NULL && second == NULL)
	{
		return;
	}
	TreeNode* fatherNode = first->father;
	bool isExist = false;
	while (fatherNode != NULL)
	{
		if (first == fatherNode->left)
		{
			isExist = Compare(fatherNode->right, second);
		}
		else if (first == fatherNode->right)
		{
			isExist = Compare(fatherNode->left, second);
		}

		if (isExist)
		{
			return fatherNode;
		}
		else
		{
			fatherNode = fatherNode->father;
		}
	}
}

	vector<TreeNode*> firstPath;
	vector<TreeNode*> secondPath;
	TreeNode* tmpNode = first;
	while (tmpNode->father != NULL)
	{
		firstPath.push_back(tmpNode);
		tmpNode = tmpNode->father;
	}
	tmpNode = second;
	while (tmpNode->father != NULL)
	{
		secondPath.push_back(tmpNode);
		tmpNode = tmpNode->father;
	}

	// 从后向前找到最近的父节点
	int firstIndex = firstPath.size() - 1;
	int secondIndex = secondPath.size() - 1;
	while (firstPath[firstIndex] == secondPath[secondIndex])
	{
		--firstIndex;
		--secondIndex;
	}
	return firstIndex[firstIndex + 1];