[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/

leetcode - Construct Binary Tree from Preorder and Postorder Traversal

문제 유형: 트리, 분할 정복

문제 난이도: Medium

 

문제

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

 

두 개의 정수 배열 preorder와 postorder가 주어집니다.

각각 같은 이진트리의 전위순회와 후위순회의 결과입니다.

그 정보를 이용해서 이진트리를 복원하시오.

만약 정답이 여러개라면, 아무거나 하나 만드시오.

 

풀이

현재 서브트리의 preorder의 왼쪽부분을 prel, 오른쪽부분을 prer이라고 두자.

postorder의 왼쪽부분은 postl, postr이라고 두자.

 

서브트리의 preorder의 맨 앞 요소와 postroder의 맨 뒤의 요소는 항상 서브트리의 루트가 된다.

그리고, 나머지 부분들에 대해 왼쪽과 오른쪽으로 나누기 위해서, preorder의 맨 앞 요소의 다음 요소를 가진 인덱스를 postorder에서 찾는다. 이를 newPostr이라 하자.

그 반대인 postroder의 맨 뒤 요소의 그 앞 요소를 가진 인덱스를 preorder에서 찾는다. 이를 newPrel이라고 하자.

각각 서브트리의 왼쪽 자식 서브트리의 루트와 오른쪽 자식 서브트리의 루트가 되기 때문이다.

 

이제, 왼쪽 서브트리의 범위는 preorder에서는 [prel + 1, newPrel-1], postorder에서는 [postl, newPostr]이 되고,

오른쪽 서브트리의 범위는 preorder에서는 [newPrel, prer], postorder에서는 [newPostr+1, prer-1]이 된다.

만약 [postl, newPostr], [newPrel, prer]의 범위가 같다면, 한쪽 자식만 있는경우이므로, 그냥 왼쪽으로 호출한다.

 

각각 재귀호출해서 현재 서브트리의 루트의 왼쪽자식, 오른쪽자식으로 한다.

현재 서브트리의 루트를 반환한다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int n;
    TreeNode* constructTree(int prel, int prer, int postl, int postr, vector<int>& preorder, vector<int>& postorder) {
    	// 유효하지 않은 범위면 null반환
        if(prel > prer || postl > postr) return nullptr;

		// 확신의 리프 노드이면, 즉시 반환
        auto root = new TreeNode(preorder[prel]);
        if(prel == prer && postl == postr) return root;

        int newprel = prel;
        while(preorder[newprel] != postorder[postr-1]) newprel++;
        int newpostr = postr;
        while(postorder[newpostr] != preorder[prel+1]) newpostr--;

		// 한쪽 자식 서브트리만 있는 경우
        if(prel + 1 == newprel && postr-1 == newpostr) {
            root -> left = constructTree(newprel, prer, postl, newpostr, preorder, postorder);
            return root;
        }

        root -> left = constructTree(prel+1, newprel-1, postl, newpostr, preorder, postorder);
        root -> right = constructTree(newprel, prer, newpostr+1, postr-1, preorder, postorder);
        return root;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        n = preorder.size();
        return constructTree(0, n-1, 0, n-1, preorder, postorder);
    }
};

 

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func constructTree(prel, prer, postl, postr int, preorder, postorder []int) *TreeNode {
    if prel > prer || postl > postr {
        return nil
    }

    root := &TreeNode{Val: preorder[prel]}
    if prel == prer && postl == postr {
        return root
    }

    newPrel := prel
    newPostr := postr
    for preorder[newPrel] != postorder[postr-1] {
        newPrel++
    }
    for postorder[newPostr] != preorder[prel+1] {
        newPostr--
    }

    if prel+1 == newPrel && postr-1 == newPostr {
        root.Left = constructTree(newPrel, prer, postl, newPostr, preorder, postorder)
        return root
    }

    root.Left = constructTree(prel+1, newPrel-1, postl, newPostr, preorder, postorder)
    root.Right = constructTree(newPrel, prer, newPostr+1, postr-1, preorder, postorder)
    return root
}

func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
    n := len(preorder)
    return constructTree(0, n-1, 0, n-1, preorder, postorder)
}