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.

解题思路

一般遇到二叉树的题都用递归求解。很明显，先序和后序复原的二叉树是不唯一，我们只需要根据某种规律恢复可能的一种二叉树。如，可以根据先序遍历找到第一个子树的头结点，作为左子树。

AC 代码

/** * 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 {
    TreeNode* constructFromPrePost(vector<int>& pre, int prebeg, int preend, 
                                  vector<int>& post, int postbeg, int postend)
    {
        if(prebeg >= preend) return nullptr;

        TreeNode* curNode = new TreeNode(pre[prebeg]);

        // 左子树
        if(prebeg + 1 == preend) return curNode;
        size_t leftRootIdx = postbeg;
        while(post[leftRootIdx] != pre[prebeg+1] && leftRootIdx != postend-1) ++leftRootIdx;
       // cout << pre[prebeg+1] << " " << pre[prebeg+leftRootIdx-postbeg+1] << endl;
        curNode->left = constructFromPrePost(pre, prebeg+1, prebeg+leftRootIdx-postbeg+2, 
                                             post, postbeg, leftRootIdx+1);

        // 右子树
        if(leftRootIdx + 1 == postend-1) return curNode;
        curNode->right = constructFromPrePost(pre, prebeg+leftRootIdx-postbeg+2,preend, 
                                            post, leftRootIdx+1, postend-1);

        return curNode;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return constructFromPrePost(pre, 0, pre.size(), post, 0, post.size());
    }
};