C++ implements LeetCode (889. Create a binary tree from preorder and later traversal)

[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal Create a 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 <= == <= 30
pre[] and post[] are both permutations of 1, 2, ..., .
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

This question gives a tree an array of preorder and postorder traversal. Let us reconstruct the original binary tree based on these two arrays. I have also done preorder traversal of binary trees [Binary Tree Preorder Traversal](/grandyang/p/) and postorder traversal [Binary Tree Postorder Traversal](/grandyang/p/), so I should be familiar with the order of traversal. In fact, the three most commonly used traversal methods of binary trees are preorder, in-order, and post-order traversal. As long as you know the array obtained by any two traversals, you can reconstruct the original binary tree, and they happen to appear in LeetCode. The other two are [Construct Binary Tree from Inorder and Postorder Traversal](/grandyang/p/) and [Construct Binary Tree from Preorder and Inorder Traversal](/grandyang/p/). If you have done the previous two questions, then this question will not be difficult. If not, it may still be tricky, although this is just a Medium question.

We know that the order of the first order traversal is root->left->right, and the order of the order of the later order traversal is left->right->root. Since you want to build a tree, you must start from the root node and then create left and right sub-nodes. If you have done many tree-related questions, you will know that most of them are done with recursion. Then when creating it, you will also call recursion to create the left and right sub-nodes. It’s good to have such a concept in your mind, and you can continue to look for this repetitive pattern. Due to the characteristics of preorder and order, the position of the root node is fixed, which is both the first and the last of the array of preorder traversal and the last of the array of postorder traversal. If we are given an array of in-order traversal, then the position of the root node can only be found from another preorder or later array. However, in-order also has the benefits of in-order. The root node just divides the left and right subtrees, so I won't go into details here. Let's go back to this question. After knowing the location of the root node, we need to separate the intervals of the left and right subtrees. The intervals in the precedent and later order are expressed as follows:

preorder -> [root] [left subtree] [right subtree]
postorder -> [left subtree] [right substree] [root]

The specific examples in the question are:

preorder -> [1] [2,4,5] [3,6,7]
postorder -> [4,5,2] [6,7,3] [root]

The lengths of the respective left subtree intervals in the precedent and subsequent order are definitely equal, but the number order may be different. However, if we observe carefully, we can find that the first number 2 of the precedent left subtree interval is at the last position of the left and right subtree intervals in the postcedent order, and this rule also applies to the right subtree interval. Why is this? This requires returning to the order of each traversal. The order of the precedent order traversal is root->left->right, and the order of the postcedent order traversal is left->right->root. In fact, this 2 is the root node of the left subtree. Of course, one will be at the beginning and the other will be at the end. Once this rule is discovered, you can locate the position range of the left and right subtree intervals according to it. Since you want to split an array, there are two ways, one is to really split it into small subarrays, and the other is to use a double pointer to point to the beginning and end of the sub-interval. The former method undoubtedly has a large number of array copies, which is not very efficient, so we use the second method here. Use preL and preR to represent the beginning and end positions of the left subtree interval respectively, and postL and postR to represent the beginning and end positions of the right subtree interval. Then if preL is greater than preR or postL is greater than postR, it means that the subtree interval is no longer present, and the null pointer is directly returned. Then you need to create the root node of the current tree first, and then get it through pre[preL]. Next, you need to find the position of the root node of the left subtree in post. The easiest way is to traverse the interval [postL, postR] in post, find its position idx, and then based on this idx, you can calculate that the length of the left subtree interval is len = (idx-postL)+1. Then the interval of the left subtree in the pre array is [preL+1, preL+len], and the interval of the right subtree is [preL+1+len, preR]. Similarly, the interval of the left subtree in the post array is [postL, idx], and the interval of the right subtree is [idx+1, postR-1]. After knowing this information, you can call the recursive function separately. See the code as follows:

Solution 1:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)() - 1, post, 0, (int)() - 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;
    }
};

We can also use the STL built-in find() function to find the position of the root node of the left subtree in the post. The rest are the same as the above solution, see the code as follows:

Solution 2:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)() - 1, post, 0, (int)() - 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(() + postL, () + postR + 1, pre[preL + 1]) - ();
        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;
    }
};

In order to further optimize the time complexity, we can use a HashMap in advance to establish a mapping between each element and its coordinates in the post array. In this way, in the recursive function, there is no need to search, and it can be directly taken out in the HashMap. Using space to exchange time is also a good method. See the code as follows:

Solution three:

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        unordered_map<int, int> m;
        for (int i = 0; i < (); ++i) m[post[i]] = i;
        return helper(pre, 0, (int)() - 1, post, 0, (int)() - 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;
    }
};

On the forum [lee215 Master](/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)) proposed an iterative writing method, which uses the help of the stack. In fact, just use an array to simulate the last-in first-out feature of the stack. This design idea is very clever. Now we create a binary tree in order based on the pre array. Our current strategy is to add the current node to the left child node of the top node of the stack element as long as there is no left child node, otherwise add it to the right child node and push the added node onto the stack. At the same time, we use two pointers i and j to point to the current position in the pre and post arrays respectively. If at a certain moment, the top element of the stack and post[j] are the same, it means that the current subtree has been established and all the current subtrees in the stack must be out of the stack until the conditions of the while loop are not met. In this way, after the final establishment, there is only one root node left in the stack. Just return, see the code as follows:

Solution 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 < (); ++i) {
            TreeNode *node = new TreeNode(pre[i]);
            while (()->val == post[j]) {
                st.pop_back();
                ++j;
            }
            if (!()->left) ()->left = node;
            else ()->right = node;
            st.push_back(node);
        }
        return st[0];
    }
};

Github Synchronization Address:

/grandyang/leetcode/issues/889