C++LeetCode 구현(105.우선 순위 와 중간 순서 로 이 진 트 리 만 들 기)

[LeetCode]105.Construct Binary Tree from Preorder and Inorder Traversal 은 선번 과 중 번 에 걸 쳐 이 진 트 리 를 만 듭 니 다.
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
    3
/ \
9  20
/  \
15   7
이 문 제 는 선서 와 중 서 를 이용 하여 역대로 이 진 트 리 를 만들어 야 한다.  Construct Binary Tree from Inorder and Postorder Traversal  원 리 는 기본적으로 같다.이 문 제 를 대상 으로 선착순 의 첫 번 째 순 서 는 반드시 뿌리 이기 때문에 원래 이 진 트 리 의 뿌리 노드 는 알 수 있다.문제 에서 중요 한 조건 은 나무 에 똑 같은 요소 가 없다 는 것 이다.이 조건 이 있 으 면 중간 순서 에서 뿌리 노드 의 위 치 를 정 하고 뿌리 노드 의 위치 로 중간 순 서 를 좌우 두 부분 으로 나 눌 수 있다.각각 재 귀적 으로 원 함 수 를 호출 합 니 다.코드 는 다음 과 같 습 니 다.

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) return NULL;
        int i = 0;
        for (i = iLeft; i <= iRight; ++i) {
            if (preorder[pLeft] == inorder[i]) break;
        }
        TreeNode *cur = new TreeNode(preorder[pLeft]);
        cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);
        cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);
        return cur;
    }
};

다음은 하나의 예 를 살 펴 보 겠 습 니 다.어떤 이 진 트 리 의 중간 순서 와 뒷 순 서 는 각각 다음 과 같 습 니 다.
Preorder:　  　5　　4　　11　　8　　13　　9
Inorder:　　 　11　　4　　5　　13　　8　　9
5　　4　　11　　8　　13　　9　　　　　　=>　　　　　　　　　 5
11　　4　　5　　13　　8　　9　　　　　　　　　　　　　　　　/　　\
4　　11　　 　　8　　 13　　9　　　　　　=>　　　　　　　　　5
11　　4　　　　 13　　8　　9　　 　　　　　　　　　　　　　  /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　　　　5
11　　　　　　 13　　　　9　　　　 　　　　　　　　　　　　   /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　 /     \
　　　　　　　　　　　　　　　　　　　　　　　　　　　11　　  13　　  9
이 문 제 를 풀 면 대부분 사람들 이 의문 을 가 질 수 있 습 니 다.왜 선서 와 후 서 를 옮 겨 다 니 며 이 진 트 리 를 만 들 지 않 았 습 니까?이것 은 선서 와 후 서 를 옮 겨 다 니 면서 이 진 트 리 를 유일 하 게 확정 할 수 없 기 때 문 입 니 다.예 를 들 어 다음 다섯 그루 의 나무 등 입 니 다.
1　　　　　　preorder:　　  1　　2　　3
/ \　　　　　  inorder:　　     2　　1　　3
2 3　　  　　 postorder:　　 2　　3　　1
1   　　　　preorder:　　   1　　2　　3
/ 　　　　　 inorder:　　     3　　2　　1
2 　　　　     postorder: 　　3　　2　　1
/
3
1　　　　    preorder:　　  1　　2　　3
/ 　　　　　  inorder:　　    2　　3　　1
2 　　　　　　postorder:　　3　　2　　1
\
3
       1　　　　     preorder:　　  1　　2　　3
\ 　　　　   inorder:　　    1　　3　　2
2 　　　　 postorder:　　3　　2　　1
/
3
       1　　　　     preorder:　　  1　　2　　3
\ 　　　　　inorder:　　    1　　2　　3
2 　　　　 postorder:　　3　　2　　1
\
3
위 에서 알 수 있 듯 이 먼저 1,23 의 이 진 트 리 다섯 그루 를 옮 겨 다 니 는 것 에 대해 그들의 중 서 는 모두 다 르 지만 그들의 후 서 는 똑 같 기 때문에 중 서 를 옮 겨 다 녀 야만 이 진 트 리 한 그루 를 유일 하 게 확정 할 수 있다.하지만 889 번 문 제 를 지적 하 는 동료 들 이 있 을 것 이다.  Construct Binary Tree from Preorder and Postorder Traversal  선서 와 후서 에서 이 진 트 리 를 재건 하 는 것 이 아 닙 니까?설마 블 로 거들 이 얼굴 을 톡톡 맞 았 단 말 인가?블 로 거들 의 1 세 영명 이 하루아침 에 무 너 진 것 일 까?아니,블 로 거들 은 운명 의 불공평 함 에 대해"Return any binary tree that matches the given preorder and postorder traversals."라 는 제목 의 요 구 를 자세히 살 펴 보 세 요.임의의 이 진 트 리 로 돌아 가면 되 기 때문에 블 로 거들 의 결론 과 모순 되 지 않 습 니 다.한숨 돌리 고 블 로 거들 의 만년 을 지 켜 냈 다~
Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/105
유사 한 제목:
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Postorder Traversal
참고 자료:
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34562/Sharing-my-straightforward-recursive-solution
C++구현 LeetCode(105.선서 와 중 서 를 옮 겨 다 니 며 이 진 트 리 를 만 드 는 것)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++는 선서 와 중 서 를 옮 겨 다 니 며 이 진 트 리 를 만 드 는 내용 을 실현 합 니 다.예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 지원 바 랍 니 다!