면접 문제 06: 이원 트 리 에서 특정한 값 의 모든 경 로 를 찾 습 니 다 (미 완성 대기)

2309 단어
제목: 정수 하나 와 이원 수 한 그루 를 입력 하 세 요.나무의 뿌리 결점 부터 아래로 내 려 가서 잎 결점 이 지나 가 는 모든 결점 이 하나의 경 로 를 형성한다.입력 정수 와 같은 모든 경 로 를 출력 합 니 다.예 를 들 어 정수 22 와 아래 이원 수 10 / \ 5 12 / \ 4 7 을 입력 하면 두 가지 경 로 를 출력 합 니 다. 10, 12 와 10, 5, 7.이원 트 리 노드 의 데이터 구 조 는 다음 과 같이 정의 합 니 다.
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
}

분석: 우선 생각 나 는 것 은 중 서 를 옮 겨 다 니 는 것 이다.
void FindPath(BinaryTreeNode* pTreeNode,int expectedSum,vector<BinaryTreeNode*> &path,int &sum){
    if(root==NULL){
        return;
    }

    BinaryTreeNode* pNode=root;
    vector<BinaryTreeNode*> path;
    int sum=0;

    sum+=pNode->m_nValue;
    path.push_back(pNode);

    bool isLeaf=(pNode->m_pLeft==NULL && pNode->m_pRight==NULL);
    if(isLeaf && sum==expectedSum){
        for(int i=0;i<path.size();i++){
            cout<<path[i]->m_nValue<<ends;
        }
    }else{
        if(pNode->p_mLeft!=NULL){
            FindPath(pNode->p_mLeft,expectedsum,path,sum);
        }
        if(pNode->p_mRight!=NULL){
            FindPath(pNode->p_mRight,expectedsum,path,sum);
        }
    }

    //return to its parent
    sum-=pNode->m_nValue;
    path.pop_back();
}

좋은 웹페이지 즐겨찾기