검 지 offer - 이 진 트 리 재건

검 지 offer - 이 진 트 리 재건
이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 다시 만 들 고 돌아 갑 니 다.
블 로그 의 코드 는 모두 우 객 C + + 11 (clang + 3.9) 에서 통과 되 었 다.
처음 이 문 제 를 풀 었 을 때 정말 갈 피 를 잡 을 수 없 었 습 니 다. 주로 앞 순서 와 중 서 를 옮 겨 다 니 는 특징 을 이해 하지 못 했 습 니 다. 나중에 소 손님 이 쓴 코드 를 보고 나 서 야 갑자기 밝 아 졌 습 니 다. 그 다음 에 구체 적 으로 설명 하 겠 습 니 다.
먼저, 앞 순 서 를 옮 겨 다 니 는 첫 번 째 숫자 는 바로 이 진 트 리 뿌리 노드 의 값 이 고 중간 순 서 는 중간 에 있 으 며 왼쪽 은 왼쪽 서브 트 리 의 값 이 고 오른쪽 은 오른쪽 서브 트 리 의 값 이 며 이 특성 을 결합 하여 이 진 트 리 를 재건 하 는 것 을 알 아야 한다.
  • 우 리 는 스스로 함 수 를 쓸 수 있 습 니 다. 두 서열 이 들 어 오 는 동시에 두 서열 의 시작 과 끝 위치 에 표 시 됩 니 다. (주로 우리 가 좌우 서브 트 리 를 구축 하 는 범 위 를 제어 하 는 데 사 용 됩 니 다) 특정한 서열 의 시작 위치 가 종료 위치 보다 클 때 nullptr
  • 로 돌아 갑 니 다.
  • 함수 내부 에서 먼저 앞의 순서 로 첫 번 째 숫자 를 옮 겨 다 니 며 만 든 뿌리 노드 에 값 을 부여 하고 중간 순서 로 이 숫자 와 같은 위 치 를 찾 습 니 다. 즉, 중간 순서 로 중간 노드 를 옮 겨 다 니 는 위치
  • 입 니 다.
  • 찾 은 후에 그 좌우 에 각각 좌우 서브 트 리 의 중간 순서 서열 이다. 이때 우 리 는 문 제 를 두 개의 작은 이 진 트 리 를 재건 하 는 것 으로 나 눌 수 있다. 재 귀 하 는 방법 으로 계속 깊이 들 어가 이 진 트 리 의 모든 노드 를 점차적으로 구축 하여 이 진 트 리 의 재건 을 실현 할 수 있다
  • .
    코드 는 다음 과 같 습 니 다:
    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            //                 ,    nullptr
            if(0 == pre.size() || 0 == vin.size())
                return nullptr;
            //      ,                 
            TreeNode* ret = reConstructBinaryTree1(pre,0,pre.size()-1,vin,0,vin.size()-1);
            return ret;
    
        }
    public:
        TreeNode* reConstructBinaryTree1(vector<int> pre,int p1,int p2,vector<int> vin,int v1,int v2)
        {
            //                    ,  nullptr
            if(p1>p2 || v1>v2)
                return nullptr;
            //      ,                 
            TreeNode* root = new TreeNode(pre[p1]);
            
            //                ,            
            for(int i=v1;i<=v2;++i)
            {
                if(pre[p1] == vin[i])
                {
                    //            ,          (    i-v1   )              (       )     
                    root->left = reConstructBinaryTree1(pre,p1+1,p1+i-v1,vin,v1,i-1);
                    //            ,          (    i-v1+1       )              (       )     
                    root->right = reConstructBinaryTree1(pre,p1+i-v1+1,p2,vin,i+1,v2);
                }
            }
            
            return root;
        }
    };
    

    좋은 웹페이지 즐겨찾기