C++LeetCode 구현(889.선번 과 후 번 을 옮 겨 다 니 며 이 진 트 리 만 들 기)

[LeetCode]889.Construct Binary Tree from Preorder and Postorder Traversal 은 선번 과 후 번 을 옮 겨 다 니 며 이 진 트 리 를 만 듭 니 다.
Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.
Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7] 
Note:

1 <= pre.length == post.length <= 30

pre[] and post[] are both permutations of 1, 2, ..., pre.length.

It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

이 문 제 는 나무의 선착순 과 후 서 를 옮 겨 다 니 는 배열 을 주 었 습 니 다.우 리 는 이 두 배열 에 따라 원래 의 이 진 트 리 를 재건 합 니 다.전에 도 이 진 트 리 의 선착순 을 해 봤 어 요.[Binary Tree Preorder Traversal](http://www.cnblogs.com/grandyang/p/4146981.html)과 뒷 순 서 를 옮 겨 다 니 며[Binary Tree Postorder Traversal](http://www.cnblogs.com/grandyang/p/4251757.html)그래서 그 순서 가 낯 설 지 않 아야 한다.사실 이 진 트 리 가 가장 자주 사용 하 는 세 가지 옮 겨 다 니 는 방식 은 먼저 순서,중간 순서,그리고 뒷 순 서 를 옮 겨 다 니 는 것 이다.그 중의 임 의 두 가지 옮 겨 다 니 는 배열 만 알 면 원시 적 인 이 진 트 리 를 재건 할 수 있 고 모두 LeetCode 에 나타 날 수 있다.다른 두 가 지 는[Construct Binary Tree from Inorder and Postorder Traversal](https://www.cnblogs.com/grandyang/p/4296193.html)와[Construct Binary Tree from Preorder and Inorder Traversal](https://www.cnblogs.com/grandyang/p/4296500.html)。앞의 두 문 제 를 풀 었 다 면 이 문 제 는 어렵 지 않 았 을 것 이다.없 었 다 면 약간의 tricky 가 있 었 을 것 이다.비록 이것 은 하나의 Medium 문제 이지 만.
우 리 는 먼저 뿌리->왼쪽->오른쪽 순 서 를 옮 겨 다 니 는 것 을 알 고 있 습 니 다.그 다음 에 순서대로 옮 겨 다 니 는 순 서 는 왼쪽->오른쪽->뿌리 입 니 다.나 무 를 만 들 려 면 뿌리 결점 부터 만 든 다음 에 좌우 부분 결점 을 만들어 야 합 니 다.만약 에 나무 와 관련 된 문 제 를 많이 풀 었 다 면 대부분 재 귀적 으로 만 들 었 다 는 것 을 알 게 될 것 입 니 다.그럼 만 들 때 도 좌우 하위 노드 호출 재 귀적 으로 만 듭 니 다.마음속 에 이런 개념 이 있 었 으 면 좋 겠 다.이 반복 되 는 pattern 을 계속 찾 아 볼 수 있다.선서 와 후 서 는 각자 의 특징 으로 인해 뿌리 결점 의 위 치 는 고정 되 어 있 습 니 다.선서 가 배열 의 첫 번 째 이자 후 서 는 배열 의 마지막 을 옮 겨 다 니 는 것 입 니 다.만약 에 우리 에 게 중 서 를 옮 겨 다 니 는 배열 이 라면 뿌리 결점 의 위 치 는 다른 선서 나 자 후 서 의 배열 에서 만 찾 을 수 있 지만 중 서 는 중 서 의 장점 도 있 습 니 다.그 뿌리 는 마침 좌우 자 나 무 를 나 누 었 으 니 여기 서 자세히 말 하지 않 고 본론 으로 돌아 가 는 것 이 좋 겠 다.뿌리 결점 의 위 치 를 알 게 된 후,우 리 는 좌우 자수의 구간 을 구분 해 야 한다.선서 와 후서 의 각 구간 은 다음 과 같다.
preorder -> [root] [left subtree] [right subtree]
postorder -> [left subtree] [right substree] [root]
구체 적 으로 문제 중의 예 는 다음 과 같다.
preorder -> [1] [2,4,5] [3,6,7]
postorder -> [4,5,2] [6,7,3] [root]
선서 와 후 서 에서 각자 의 왼쪽 나무 구간 의 길 이 는 틀림없이 같 을 것 이다.그러나 그 숫자 순 서 는 다 를 수 있다.그러나 우리 가 자세히 살 펴 보면 선서 왼쪽 나무 구간 의 첫 번 째 숫자 2 가 후 서 좌우 나무 구간 의 마지막 위치 에 있 고 이 규칙 이 오른쪽 나무 구간 에 똑 같이 적용 되 는 이 유 를 알 수 있다.이것 은 각자 가 옮 겨 다 니 는 순서 로 돌아 가 야 한다.먼저 옮 겨 다 니 는 순 서 는 뿌리->왼쪽->오른쪽 이 고,뒤에 옮 겨 다 니 는 순 서 는 왼쪽->오른쪽->뿌리 이다.사실 이 2 는 왼쪽 나무의 뿌리 결점 이다.당연히 하 나 는 시작 에 있 고 하 나 는 끝 에 있 을 것 이다.이 규칙 을 발견 하면 좌우 나무 구간 의 위치 범 위 를 정할 수 있다.배열 을 나 누 려 면 두 가지 방식 이 있다.하 나 는 정말 작은 하위 배열 로 나 누 는 것 이 고,다른 하 나 는 두 바늘 로 하위 구간 의 시작 과 끝 을 가리 키 는 것 이다.앞의 방법 은 의심 할 여지없이 대량의 수조 복사 가 있어 서 효율 적 이지 않 기 때문에 우 리 는 두 번 째 방법 으로 한다.preL 과 preR 로 각각 왼쪽 하위 트 리 구간 의 시작 과 끝 위 치 를 표시 하고,postL 과 postR 은 오른쪽 하위 트 리 구간 의 시작 과 끝 위 치 를 표시 하 며,preL 이 preR 보다 크 거나 postL 이 postR 보다 클 경우 하위 트 리 구간 이 존재 하지 않 는 다 는 것 을 설명 하고 빈 지침 으로 되 돌아 갑 니 다.그리고 현재 트 리 의 뿌리 결산 점 을 새로 만 들 려 면 pre[preL]를 통 해 가 져 오 면 됩 니 다.그 다음 에 왼쪽 트 리 의 뿌리 결산 점 이 post 에 있 는 위 치 를 찾 으 려 면 가장 쉬 운 방법 은 post 의 구간[postL,postR]을 옮 겨 다 니 며 그 위치 idx 를 찾 은 다음 에 이 idx 에 따라 왼쪽 트 리 구간 의 길 이 를 len=(idx-postL)+1 로 계산 할 수 있 습 니 다.그러면 pre 배열 의 왼쪽 하위 트 리 구간 은[preL+1,preL+len]이 고 오른쪽 하위 트 리 구간 은[preL+1+len,preR]이 며,마찬가지 로 post 배열 의 왼쪽 하위 트 리 구간 은[postL,idx]이 며,오른쪽 하위 트 리 구간 은[idx+1,postR-1]입 니 다.이 정 보 를 알 면 재 귀 함 수 를 각각 호출 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = -1;
        for (idx = postL; idx <= postR; ++idx) {
            if (pre[preL + 1] == post[idx]) break;
        }
        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
        return node;
    }
};

또한 STL 에 내 장 된 find()함 수 를 사용 하여 왼쪽 하위 트 리 의 뿌리 노드 가 post 에 있 는 위 치 를 찾 을 수 있 습 니 다.나머지 부분 은 위의 해법 과 같 습 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = find(post.begin() + postL, post.begin() + postR + 1, pre[preL + 1]) - post.begin();
        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
        return node;
    }
};

시간의 복잡 도 를 더욱 최적화 하기 위해 우 리 는 먼저 HashMap 을 사용 하여 post 배열 의 모든 요소 와 좌표 간 의 매 핑 을 구축 할 수 있 습 니 다.그러면 재 귀 함수 에서 찾 지 않 고 HashMap 에서 그 위 치 를 직접 꺼 내 사용 하면 됩 니 다.공간 으로 시간 을 바 꾸 는 것 도 좋 은 방법 입 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        unordered_map<int, int> m;
        for (int i = 0; i < post.size(); ++i) m[post[i]] = i;
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1, m);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR, unordered_map<int, int>& m) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = m[pre[preL + 1]], len = (idx - postL) + 1;
        node->left = helper(pre, preL + 1, preL + len, post, postL, idx, m);
        node->right = helper(pre, preL + 1 + len, preR, post, idx + 1, postR - 1, m);
        return node;
    }
};

포럼 에서[lee 215 대신](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-one-pass-real-O(N)는 스 택 을 빌려 만 들 었 는데 사실은 하나의 배열 로 하면 되 고 스 택 의 후진 이 먼저 나 오 는 특성 을 모 의 했다.이런 디자인 사고방식 은 매우 교묘 하 다.현 재 는 pre 수조 에 따라 먼저 두 갈래 나 무 를 만든다.현재 우리 의 전략 은 창고 꼭대기 에 왼쪽 노드 가 없 으 면 현재 노드 를 창고 꼭대기 원소 의 왼쪽 노드 에 추가 하고 그렇지 않 으 면 오른쪽 노드 에 추가 하고 가 입 된 노드 를 창고 에 눌 러 넣 는 것 이다.이 동시에 우 리 는 두 개의 포인터 i 와 j 로 현재 pre 와 post 배열 에 있 는 위 치 를 가리 키 고 있 습 니 다.만약 에 어느 순간 에 스 택 꼭대기 요소 와 post[j]가 같 으 면 현재 하위 트 리 가 이미 구축 되 었 음 을 설명 합 니 다.스 택 에 있 는 현재 하위 트 리 를 모두 스 택 에서 내 보 내 고 while 순환 조건 이 만족 하지 않 을 때 까지 해 야 합 니 다.이렇게 최종 적 으로 세 워 지면 스 택 에 하나의 노드 만 남 았 습 니 다.돌아 오 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        vector<TreeNode*> st;
        st.push_back(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.size(); ++i) {
            TreeNode *node = new TreeNode(pre[i]);
            while (st.back()->val == post[j]) {
                st.pop_back();
                ++j;
            }
            if (!st.back()->left) st.back()->left = node;
            else st.back()->right = node;
            st.push_back(node);
        }
        return st[0];
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/889
유사 한 제목:
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
참고 자료:
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161286/C%2B%2B-O(N)-recursive-solution
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/163540/Java-recursive-solution-beat-99.9
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)
C++구현 LeetCode(889.선번 과 후 번 에 이 진 트 리 를 만 듭 니 다)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++는 선번 과 후 번 에 이 진 트 리 를 만 드 는 내용 을 실현 합 니 다.예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 보 세 요.앞으로 많은 응원 바 랍 니 다!