C++LeetCode 구현(106.중 서 와 후 서 를 옮 겨 다 니 며 이 진 트 리 만 들 기)

[LeetCode]106.Construct Binary Tree from Inorder and Postorder Traversal 은 중간 순서 와 뒷 순서 로 이 진 트 리 를 만 듭 니 다.
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
    3
/ \
9  20
/  \
15   7
이 문 제 는 중 서 와 후 서 를 옮 겨 다 니 는 결과 로 원 두 갈래 나 무 를 재건 해 야 한 다 는 것 을 알 고 있 습 니 다.우 리 는 중 서 의 옮 겨 다 니 는 순서 가 왼쪽-뿌리-오른쪽 이 고 후 서 는 왼쪽-오른쪽-뿌리 라 는 것 을 알 고 있 습 니 다.이런 나무의 재건 은 보통 재 귀 를 통 해 이 루어 집 니 다.블 로 거 이전의 블 로 그 를 참조 할 수 있 습 니 다.  Convert Sorted Array to Binary Search Tree 。이 문제 에 대해 뒷 순 서 는 마지막 에 뿌리 가 분명 하기 때문에 원래 이 진 트 리 의 뿌리 결점 을 알 수 있다.문제 에서 중요 한 조건 은 나무 에 똑 같은 요소 가 없다 는 것 이다.이 조건 이 있 으 면 중간 순 서 를 옮 겨 다 니 면서 뿌리 노드 의 위 치 를 정 하고 뿌리 노드 의 위치 로 중간 순 서 를 좌우 두 부분 으로 나 눌 수 있다.각각 재 귀적 으로 원 함 수 를 호출 하 다.코드 는 다음 과 같 습 니 다:

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

상기 코드 에서 조심해 야 할 부분 은 재 귀 는 postorder 의 좌우 index 입 니 다.예 를 들 어 pLeft+i-iLeft-1 입 니 다.이것 은 길 고 기억 하기 어렵 습 니 다.먼저 i-iLeft 는 inorder 의 뿌리 노드 위치 와 왼쪽 시작 점 의 거 리 를 계산 한 다음 에 postorder 왼쪽 시작 점 을 더 한 다음 에 1 을 줄 여야 한 다 는 것 을 기억 해 야 합 니 다.우 리 는 이렇게 분석 할 수 있 습 니 다.만약 에 뿌리 결점 이 왼쪽 의 시작 점 이 라면 나 누 면 왼쪽 서열 은 빈 집합 이 어야 합 니 다.이때 i-iLeft 는 0 이 고 pLeft+0-1다음은 하나의 예 를 살 펴 보 겠 습 니 다.어떤 이 진 트 리 의 중간 순서 와 뒷 순 서 는 각각 다음 과 같 습 니 다.
Inorder:　　 　11　　4　　5　　13　　8　　9
Postorder:　　11　　4　　13　　9　　8　　5　　
11　　4　　5　　13　　8　　9　　　　　　=>　　　　　　　　　 5
11　　4　　13　　9　　8　　5　　　　　　　　　　　　　　　　/　　\
11　　4　　 　　13　　 8　　9　　　　　　=>　　　　　　　　　5
11　　4　　　　 13　　9　　8　　 　　　　　　　　　　　　　  /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　　　　5
11　　　　　　 13　　　　9　　　　 　　　　　　　　　　　　   /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　 /     \
　　　　　　　　　　　　　　　　　　　　　　　　　　　11　　  13　　  9
Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/106
유사 한 제목:
Construct Binary Tree from Preorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
참고 자료:
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/758462/C%2B%2B-Detail-Explain-or-Diagram
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/34803/Sharing-my-straightforward-recursive-solution
C++구현 LeetCode(106.중 서 와 후 서 를 옮 겨 다 니 며 이 진 트 리 를 만 드 는 것)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++는 중 서 와 후 서 를 옮 겨 다 니 며 이 진 트 리 를 만 드 는 내용 을 실현 합 니 다.예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 지원 바 랍 니 다!