검지 OFFER 면접문제 6: 전순과 중순에 따라 두 갈래 나무 구축

앞 순서와 중간 순서에 따라 두 갈래 트리를 구축하다

사전 요구 사항 요약

전순(preorder) 중순(inorder)에 따라 두 갈래 트리를 구축하는 원리는 본 코드도 귀속을 통해 이루어지지만 전송된 매개 변수는 약간 다르다.각각preorder수조의 첫 번째 주소, 하위 트리가preorder구간에 대응하는 초기 하표,inorder수조의 첫 번째 주소, 하위 트리가inorder구간에 대응하는 초기 하표와 하위 트리가 대응하는 구간의 길이입니다.이 다섯 개의 매개 변수에 근거하여 우리는 하위 나무가 있는 구간을 확정할 수 있다.분명히preorder수조와inorder수조에서 서브트리가 대응하는 구간의 길이는 같고 순서만 다르기 때문에 나머지 작업은 서브트리가 대응하는 구간이preorder수조와inorder의 위치를 찾아내는 것이다.

nRoot Value Offset의 역할

nRootValueOffset 현재 구간의 부 노드가 inoder 수조에서 상대적인 inorder_start의 편이, 예를 들어 귀속되지 않은 상위 노드 값은 1이고,inorder 그룹에서 상대inorder_start의 편이는 3입니다.이 값에 근거하여 우리는 inorder 수조에서 부모 노드의 왼쪽에 있는 구간은 왼쪽 나무에 속하고 오른쪽 구간은 오른쪽 나무에 속한다고 판단할 수 있다.그리고 왼쪽 트리의 구간 크기는 nRootValueOffset, 오른쪽 트리의 구간 크기는 총 구간 크기nLength와 같고 편이량과 부모 노드, 즉 nLength-1-nRootValueOffset을 뺀다.

어떻게 한 노드에 왼쪽 나무나 오른쪽 나무가 있는지 판단합니까

inorder 배열에서:

오프셋이 발생하면 반드시 왼쪽 트리가 존재하고 왼쪽 트리가 오프셋 좌표 왼쪽에 있음

만약 편이량이 최대, 즉 nLength-1에 이르면 오른쪽 트리가 존재하지 않는다.반대로 오프셋 값이 최대에 도달하지 않으면 오른쪽 트리가 존재합니다

preoder 수조에서 왼쪽 트리 구간과 오른쪽 트리 구간의 시작 위치를 찾습니다

preorder 수조 구조는'부모 노드 + 왼쪽 트리 + 오른쪽 트리'이기 때문에 왼쪽 트리 구간의 시작은 반드시 아버지 노드의 다음 위치에 있다. 아버지 노드는 preorder 수조 중 현재 구간의 시작 위치이다. preorder_start, 왼쪽 트리 구간의 시작 위치는 preorder_start+1, 오른쪽 트리 구간의 초기 위치는 왼쪽 트리 구간의 시작 위치에 글자 길이를 더한다. preorder_start+nRootValueOffset+1

inorder 수조에서 왼쪽 트리 구간과 오른쪽 트리 구간의 시작 위치를 찾습니다

order 수조 구조는'왼쪽 트리 + 부모 노드 + 오른쪽 트리'로 왼쪽 트리 구간의 시작 위치가 현재 구간의 시작 위치임을 쉽게 알 수 있다. inorder_start, 오른쪽 트리 구간의 시작 위치는 현재 구간의 시작 위치이고 왼쪽 트리의 길이와 부모 노드를 더한다. inorder_start+nRootValueOffset+1코드는 다음과 같습니다.

BinaryTreeNode* buildTree(int preorder[],int preorder_start,int inorder[],int inorder_start,int nLength){
    if(preorder==NULL || inorder==NULL || preorder_start<=0 || inorder_start<=0 || nLength<=0 )
        return NULL;
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = preorder[preorder_start];
    int nRootValueOffset=0; 
    
    // 
    for(int i=inorder_start;im_nValue) break;
        nRootValueOffset++;
    }
    if(nRootValueOffset>0)
        root->m_pLeftChild=buildTree(preorder,preorder_start+1,inorder,inorder_start,nRootValueOffset);
    else root->m_pLeftChild=NULL;

    if(nRootValueOffsetm_pRightChild=buildTree(preorder,preorder_start+nRootValueOffset+1,inorder,inorder_start+nRootValueOffset+1,nLength-1-nRootValueOffset);
    else root->m_pRightChild=NULL;

    return root;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.