二叉の木の最近の公共の祖先、2つの最も遠いノード、第K層の結点の個数、出現回数が半分を超える要素

1.結点の最近の共通祖先の考え方:2つのノードのパスを保存し、同じルートノードを判断する

typedef BNode TreeNode;

bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list&list)
{
    //    ，     pop
    if (pHead == pNode)
    {
        return true;
    }

    list.push_back(pHead);
    bool found = false;


    //    
    if (pHead->pLeft)
    {
        found = GetNodePath(pHead->pLeft, pNode, list);
    }

    if (!found&&pHead->pRight)
    {
        found = GetNodePath(pHead->pRight, pNode, list);
    }

    if (!found)
    {
        list.pop_back();
    }
    return found;

}

//       
TreeNode* GetLastCommon
   (
    const std::list&path1,
    const std::list&path2
    )
{
    std::list::const_iterator it1 = path1.begin();
    std::list::const_iterator it2 = path2.begin();

    TreeNode* pLast = NULL;
    while (it1 != path1.end() && it2 != path2.end())
    {
        if (*it1 == *it2)
        {
            pLast = *it1;
        }
        else
        {
            break;
        }
        it1++;
        it2++;
    }
    return pLast;

}


TreeNode* LastCommonParent(TreeNode*pHead, TreeNode* pNode1, TreeNode* pNode2)
{
    if (pHead == NULL || pNode1 == NULL || pNode2 == NULL)
    {
        return NULL;
    }

    //      
    std::listpath1;
    GetNodePath(pHead,pNode1,path1);

    std::listpath2;
    GetNodePath(pHead, pNode2, path2);


    return GetLastCommon(path1,path2);
}

2.最も遠い2つの結点の距離は構想を実現します.2つの結点の一番遠い距離は、左右の子樹の高さの和です.最大値は下から上へ求めて、後から順に遍歴します.

size_t GetFarthestDistance(TreeNode* pHead,size_t&maxLength)
{
    if (pHead == NULL)
    {
        return 0;
    }
    size_t left=GetFarthestDistance(pHead->pLeft,maxLength);
    size_t right=GetFarthestDistance(pHead->pRight,maxLength);

    if (left + right > maxLength)
    {
        maxLength = left + right;
    }

    return left > right ? left + 1 : right + 1;
}

3.葉っぱのノードの数の考え方:一回の木を遍歴して、左右の子供が全部空になったら、葉っぱのノードとして数えます.

void _GetLeafCount(BNode*  pRoot,size_t&count)
{
    if (pRoot)
    {
        if (!(pRoot->pLeft) && !(pRoot->pRight))
        {
            count++;
        }
        _GetLeafCount(pRoot->pLeft, count);
        _GetLeafCount(pRoot->pRight, count);
    }

}

4.K層ノードの個数

void _GetKthLeafCount(BNode*  pRoot,size_t k,size_t K, size_t&count)
{
    if (pRoot)
    {
        if (k==K)
        {
            count++;
        }
        k++;
        _GetKthLeafCount(pRoot->pLeft,k,K ,count);   //       ，       ++   
        _GetKthLeafCount(pRoot->pRight,k,K, count);
    }
}

5.1つの配列のうち、1つの数字が配列の半分を超えています.この文字を求めます.例えば:int a[]={2,3,2,2,2,2,2,5,4,1,2,3}を求めて、半分以上の数字は2です.考え方1:カウンタを使って、一つの保存値を等しい場合、＋＋を行います.等しくない場合、−1に等しい場合、更新を行います.

size_t GetHalfTimesNum1(int* arr,size_t size)
{
    if (arr == NULL || size < 1)
    {
        return 0;
    }
    int num = arr[0];
    int count = 0;

    for (int i = 0; i < size; i++)
    {
        if (num == arr[i])
        {
            count++;
        }
        else
        {
            count--;
        }


        if (count < 0)
        {
            num = arr[i];
        }
    }


    return num;

}
size_t GetHalfTimesNum2(int* arr, size_t size)
{
    sort(arr, arr + size);
    return arr[size/2];
}