두 갈래 나무 필기시험 면접 문제 매듭

직장을 구하는 열기는 이미 한참이 지났다. 그 과정에서 생각해 보면 다소 알이 아프다. 크고 작은 필기시험 면접을 보는 것도 그렇고 두 갈래 나무의 문제는 기본적으로 친근감을 느낀다. 마치 만난 듯한 느낌이 든다. 자신이 풀지 않은 원제가 비슷한 원형 문제인 경우가 많다. 대부분은'검지offer'에서 찾을 수 있다. 지금 그것을 정리하면다음 문제는'검지offer'라는 책에서 발췌한 것으로 두 갈래 나무의 문제를 많이 보았고 나무의 문제는 대동소이해졌다는 것을 스스로 깨달았다. 예전에는 나무를 준비한 적이 없었지만 한 번은 나무의 큰 문제를 스스로 해결할 수 있었다. 그리고 두 갈래 나무를 만드는 동시에 귀속을 깊게 했다.
두 갈래 나무의 결점 정의는 다음과 같습니다.

class BinaryTreeNode
{
	int			m_nValue;
	BinaryTreeNode*		m_pLeft;
	BinaryTreeNode*		m_pRight;
};

1: 두 갈래 나무 재건
문제 설명: 두 갈래 나무의 앞 순서 반복 서열 (예: {1, 2, 4, 7, 3, 5, 6, 8}) 과 중간 순서 반복 서열 (예: {4, 7, 2, 1, 5, 3, 8, 6} 을 입력하여 이 두 갈래 나무를 재구성합니다.

BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
    if(preorder == NULL || inorder == NULL || length <= 0)
        return NULL;

    return ConstructCore(preorder, preorder + length - 1,
        inorder, inorder + length - 1);
}

BinaryTreeNode* ConstructCore
(
    int* startPreorder, int* endPreorder, 
    int* startInorder, int* endInorder
)
{
    //  
    int rootValue = startPreorder[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = rootValue;
    root->m_pLeft = root->m_pRight = NULL;

    if(startPreorder == endPreorder)
    {
        if(startInorder == endInorder && *startPreorder == *startInorder)
            return root;
        else
            throw std::exception("Invalid input.");
    }

    //  
    int* rootInorder = startInorder;
    while(rootInorder <= endInorder && *rootInorder != rootValue)
        ++ rootInorder;

    if(rootInorder == endInorder && *rootInorder != rootValue)
        throw std::exception("Invalid input.");

    int leftLength = rootInorder - startInorder;
    int* leftPreorderEnd = startPreorder + leftLength;
    if(leftLength > 0)
    {
        //  
        root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
            startInorder, rootInorder - 1);
    }
    if(leftLength < endPreorder - startPreorder)
    {
        //  
        root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
            rootInorder + 1, endInorder);
    }

    return root;
}

2: 나무의 자 구조
문제 설명: 두 개의 두 갈래 나무 A와 B를 입력하여 B가 A의 하위 구조인지 판단한다.

bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
    bool result = false;

    if(pRoot1 != NULL && pRoot2 != NULL)
    {
        if(pRoot1->m_nValue == pRoot2->m_nValue)
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        if(!result)
            result = HasSubtree(pRoot1->m_pLeft, pRoot2);
        if(!result)
            result = HasSubtree(pRoot1->m_pRight, pRoot2);
    }

    return result;
}

bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
    if(pRoot2 == NULL)
        return true;

    if(pRoot1 == NULL)
        return false;

    if(pRoot1->m_nValue != pRoot2->m_nValue)
        return false;

    return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
        DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}

3:두 갈래 나무의 거울
문제 설명: 두 갈래 트리를 입력하여 거울을 출력합니다.(거울을 보면 어떻게 된 일인지 알 수 있다)

void MirrorRecursively(BinaryTreeNode *pNode)
{
    if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight))
        return;

    BinaryTreeNode *pTemp = pNode->m_pLeft;
    pNode->m_pLeft = pNode->m_pRight;
    pNode->m_pRight = pTemp;
    
    if(pNode->m_pLeft)
        MirrorRecursively(pNode->m_pLeft);  

    if(pNode->m_pRight)
        MirrorRecursively(pNode->m_pRight); 
}

void MirrorIteratively(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return;

    std::stack<BinaryTreeNode*> stackTreeNode;
    stackTreeNode.push(pRoot);

    while(stackTreeNode.size() > 0)
    {
        BinaryTreeNode *pNode = stackTreeNode.top();
        stackTreeNode.pop();

        BinaryTreeNode *pTemp = pNode->m_pLeft;
        pNode->m_pLeft = pNode->m_pRight;
        pNode->m_pRight = pTemp;

        if(pNode->m_pLeft)
            stackTreeNode.push(pNode->m_pLeft);

        if(pNode->m_pRight)
            stackTreeNode.push(pNode->m_pRight);
    }
}

4: 위에서 아래로 두 갈래 나무 인쇄
문제 설명: 차원별로 두 갈래 나무의 모든 노드를 인쇄합니다.

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)
{
	if (!pTreeRoot)
		return;
	std::deque<BinaryTreeNode *> dequeTreeNode;
	dequeTreeNode.push_back(pTreeRoot);
	while (dequeTreeNode.size())
	{
		BinaryTreeNode *pNode = dequeTreeNode.front();
		dequeTreeNode.pop_front();
		printf ("%d ", pNode ->m_nValue);
		if (pNode ->m_pLeft)
			dequeTreeNode.push_back(pNode ->m_pLeft);
		if (pNode ->m_pRight)
			dequeTreeNode.push_back(pNode ->m_pRight);
	}
}

5: 두 갈래 검색 트리의 뒷차례 반복 시퀀스
문제 설명: 정수 그룹을 입력하고 (임의의 두 숫자가 같지 않음) 이 그룹이 어떤 두 갈래 검색 트리의 뒷순서가 반복되는 결과인지 판단합니다.

// BST：Binary Search Tree， 
bool VerifySquenceOfBST(int sequence[], int length)
{
    if(sequence == NULL || length <= 0)
        return false;

    int root = sequence[length - 1];

    //  
    int i = 0;
    for(; i < length - 1; ++ i)
    {
        if(sequence[i] > root)
            break;
    }

    //  
    int j = i;
    for(; j < length - 1; ++ j)
    {
        if(sequence[j] < root)
            return false;
    }

    //  
    bool left = true;
    if(i > 0)
        left = VerifySquenceOfBST(sequence, i);

    //  
    bool right = true;
    if(i < length - 1)
        right = VerifySquenceOfBST(sequence + i, length - i - 1);

    return (left && right);
}

6: 두 갈래 트리 중 하나가 되는 경로
문제 설명: 두 갈래 나무와 하나의 정수를 입력하여 두 갈래 나무의 노드 값과 이 정수의 경로를 출력하고 뿌리 노드에서 잎 노드로 하나의 경로를 형성한다.

void FindPath(BinaryTreeNode* pRoot, int expectedSum)
{
    if(pRoot == NULL)
        return;

    std::vector<int> path;
    int currentSum = 0;
    FindPath(pRoot, expectedSum, path, currentSum);
}

void FindPath
(
    BinaryTreeNode*   pRoot,        
    int               expectedSum,  
    std::vector<int>& path,         
    int&              currentSum
)
{
    currentSum += pRoot->m_nValue;
    path.push_back(pRoot->m_nValue);

    //  ， 
    //  
    bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
    if(currentSum == expectedSum && isLeaf)
    {
        printf("A path is found: ");
        std::vector<int>::iterator iter = path.begin();
        for(; iter != path.end(); ++ iter)
            printf("%d\t", *iter);
        
        printf("
");
    }

    //  ， 
    if(pRoot->m_pLeft != NULL)
        FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
    if(pRoot->m_pRight != NULL)
        FindPath(pRoot->m_pRight, expectedSum, path, currentSum);

    //  ， ，
    //  currentSum 
    currentSum -= pRoot->m_nValue;
    path.pop_back();
} 

7:두 갈래 검색 트리와 양방향 체인 테이블
문제 설명: 두 갈래 검색 트리를 입력하고 배열된 양방향 체인 테이블로 변환합니다. 지침의 방향을 조정할 수 밖에 없습니다.

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = NULL;
    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList ，
    //  
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
    if(pNode == NULL)
        return;
    
     // 
    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList; 
    if(*pLastNodeInList != NULL)
        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

8:두 갈래 나무의 깊이
문제 설명: 뿌리 노드에서 잎 노드까지 순서대로 지나가는 노드(뿌리, 잎 포함)는 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.

int TreeDepth(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)

        return 0;

    int nLeft = TreeDepth(pRoot->m_pLeft);
    int nRight = TreeDepth(pRoot->m_pRight);

    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

9: 두 갈래 나무가 균형 있는 두 갈래 나무인지 아닌지 판단
문제 설명: 만약에 어떤 한두 갈래 나무 중의 임의의 노드의 좌우 자목의 깊이 차이가 1을 초과하지 않으면 균형 두 갈래 나무이다.

// 
bool IsBalanced_Solution2(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }

    int left, right;
    if(IsBalanced(pRoot->m_pLeft, &left) 
        && IsBalanced(pRoot->m_pRight, &right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }

    return false;
}