889.Construct Binary Tree from Preorder and Postorder Traversal

Tags: Medium Tree

Links: https://leetcode.com/problems/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.

---

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = pre.size();
        return build(0, n - 1, 0, n - 1, pre, post);
    }

    TreeNode *build(int pre_start, int pre_end, int post_start, int post_end, vector<int>& pre, vector<int>& post)
    {
        if (pre_start > pre_end || post_start > post_end) return NULL;

        TreeNode *root = new TreeNode(pre[pre_start]);
        TreeNode *l = NULL, *r = NULL;

        int pos = -1, leftSize = 0;
        if (pre_start < pre_end) {
            pos = find(post.begin(), post.end(), pre[pre_start + 1]) - post.begin();
            leftSize = pos - post_start + 1;
            l = build(pre_start + 1, pre_start + leftSize, post_start, post_start + leftSize - 1, pre, post);
        }

        if (pre_start + leftSize < pre_end) {
            r = build(pre_start + 1 + leftSize, pre_end, post_start + leftSize, post_end - 1, pre, post);
        }

        root -> left = l;
        root -> right = r;
        return root;
    }
};

以题目中的数据为例：

pre:  1 2 4 5 3 6 7
post: 4 5 2 6 7 3 1

根据前面利用中序和前序来构建二叉树的思路，我们希望得到如下结构
pre: [root][leftSize][rightSize]
post:[leftSize][rightSize][root]

于是思路是首先根据pre的第一个节点构建根节点，然后去判断leftSize是否不为0，如果不为0，那么就可以递归的去构建左子树。

在post里寻找leftSize的第一个元素，那么从post_start到这个元素之间就是左子树的元素
注意每次都要去检查leftSize和rightSize是否存在，不存在则节点为NULL