编程语言_二叉树中任意两节点的最低共同父节点

通过两个和二叉树相关的算法题来看看和递归在二叉树中的应用
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
思路：如果这两个节点不在同一个子树下面，那么这棵树的根节点就是他们的共同最低父节点。
如果两个都在右子树，那么以右子树的最上面的那个节点作为根节点，重新进行判断，递归调用。
同理两个都在左子树，则方法同上。也就是说，最终的结果分别只有三种情况，一个节点在右子树，一个节点在左子树。两个节点都在右子树，两个节点都在左子树。
如果是第一种情况，那么当前的节点就是他们最低的公共节点，左右都在左子树，或者在右子树，那么就递归调用。

BinTree* GetParent(BinTree* root,BinTree* first,BinTree* second)
{
         if(root == NULL)
           return ;
         if(root == first || second == second)
         {
           return root;        
         }
         BinTree* Low_left = GetParent(root->left,first,second);
         BinTree* Low_right = GetParent(root->right,first,second);
         /*说明在左子树中没有找到和first/second中任何一个相同的节点  公共父节点右子树 而且第一个就是*/  
         if(Low_left == NULL)  
           return Low_right;
         /*在右子树中没有找到和first/second中任何一个相同的节点 公共父节点在左子树 而且第一个就是最低父节点*/
         else if(Low_right == NULL)
           return Low_left;
         else
            return root;
 }

在左子树中没找到任何一个节点，那么就在右子树中找，在右子树中没找到任何一个节点，那么共同父节点肯定在左子树。如果在左右子树中各找到一个节点（注意并不可能同时找到两个节点的），那么当前节点就是最低共同父节点。
二叉树中任意两个节点的最远距离
这里的距离就是边的个数。
我们也同样可以使用递归来解决。所有的情况就是，最远的两个节点一个在左子树，一个在右子树，那么就是左子树中最远节点到当前节点的距离加上右子树中最远节点到当前节点的距离，也就是说最远距离跨越了根节点。第二种情况就是最远距离的两个节点都在右子树，那么我们就需要看右字数中任意两点的最远距离，第三种情况就是最远距离的两个节点都在左子树，那么我们就需要计算左子树中最远距离。然后比较三种情况中最远的距离即可

/*
  distance 是以root为根的的树，左子树到root的距离和右子树到root的距离的和  
  函数的返回值就是以root为跟的树 任意两点的最远距离 函数内部进行了比较选择
*/
int Distance(BinTree* root,int& distance)
{
    if( root == NULL)
    {
        distance = 0;
        return ; 
    }
    int left,right;
    int left_dis = Distance(root->left,left);
    int right_dis = Distance(root->right,right);
    distance = (left > right? left :right)+1;
    
    return max(left_dis,max(right_max,left+right));
}

另外一种更加直观的比较：

int MaxDepth(BinTree* root)
{
    int depth = 0;
    if(root != NULL)
    {
       int left_depth = MaxDepth(root->left);
       int right_depth = MaxDepth(root->right);
       depth = left_depth > right_depty? left_depth : right_depth;
       depth++; 
    }
    return depth;
    }

int MaxDistance(BinTree* root)
{
    int maxdis = 0;
    if(root != NULL)
    {
        maxdis = MaxDepth(root->right) +MaxDepth(root->left);
        int left_dis = MaxDistance(root->left);
        int right_dis = MaxDistance(root->right);
        int temp = left_dis >  right_dis? left_dis:right_dis;
        maxdis = temp>maxdis ? temp :maxdis;
    }
    return maxdis;
    }