889.Construct Binary Tree from Preorder and Postorder Traver

发布时间：2020-12-14 04:17:35 所属栏目：大数据来源：网络整理

导读：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,7,1] Output: [1,7] ? Note: 1 = p

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,7,1] Output: [1,7]

Note:

1 <= pre.length == post.length <= 30
pre[]?and?post[]?are both permutations of?1,...,pre.length.
It is guaranteed an answer exists. If there exists multiple answers,you can return any of them.

Runtime:?8 ms,faster than?98.12%?of?C++?online submissions for Construct Binary Tree from Preorder and Postorder Traversal.

#include<stdlib.h>
#include<vector>
#include<stack>
#include<queue>
#include <iostream>

using namespace std;

//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) {
        if (pre.size() == 0) return nullptr;
        stack<TreeNode *> st;
        TreeNode *root = new TreeNode(pre[0]);
        st.push(root);
        int j = 0;
        int i = 0;
        TreeNode *node = nullptr;
        for(int i=1;i<pre.size();++i){
            while (st.top()->val == post[j]) {
                node = st.top();
                st.pop();
                printf("pop %dn",node->val);
                if (st.top()->left == nullptr) {
                    st.top()->left = node;
                    printf("%d left child is %dn",st.top()->val,node->val);
                } else {
                    st.top()->right = node;
                    printf("%d right child is %dn",node->val);
                }
                j++;
                printf("j: %dn",j);
            }
            if (i < pre.size()){
                st.push(new TreeNode(pre[i]));
                printf("push %dn",pre[i]);
            }
        }

        while (true) {
            node = st.top();
            st.pop();
            if(st.empty()) break;
            printf("pop %dn",node->val);
            if (st.top()->left == nullptr) {
                st.top()->left = node;
                printf("%d left child is %dn",node->val);
            } else {
                st.top()->right = node;
                printf("%d right child is %dn",node->val);
            }
            j++;
            printf("j: %dn",j);
        }
        return root;
//        printf("returnn");
//        printf("root->value %dn",root->val);
//        return root;
    }
};

void show_tree(TreeNode *root) {
    if (root == nullptr) {
        cout<<"root is nullptr"<<endl;
        return;
    }
    cout<<"root is not nullptr"<<endl;
    queue<TreeNode *> qu;
    qu.push(root);
    int sz;
    while (!qu.empty()) {
        sz = qu.size();
        TreeNode* node= nullptr;
        for (int i = 0; i < sz; ++i) {
            node=qu.front();
            cout << node->val << " ";
            qu.pop();
            if (node->left)
                qu.push(node->left);
            if (node->right)
                qu.push(node->right);
        }
        cout << "n";
    }
}

int main() {
    vector<int> pre{1,2,4,5,3,6,7};
    vector<int> post{4,7,1};
    Solution solution;
    TreeNode *res = solution.constructFromPrePost(pre,post);

//    solution.constructFromPrePost(pre,post);
    printf("res value %dn",res->val);
    show_tree(res);
    return 0;

}

提交代码

class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &pre,vector<int> &post) {
        if (pre.size() == 0) return nullptr;
        stack<TreeNode *> st;
        TreeNode *root = new TreeNode(pre[0]);
        st.push(root);
        int j = 0;
        TreeNode *node = nullptr;
        for(int i=1;i<=pre.size();++i){
            while (st.top()->val == post[j]) {
                node = st.top();
                st.pop();
                //printf("pop %dn",node->val);
                if(st.empty())
                    return root;
                if (st.top()->left == nullptr) {
                    st.top()->left = node;
                    //printf("%d left child is %dn",node->val);
                } else {
                    st.top()->right = node;
                    //printf("%d right child is %dn",node->val);
                }
                j++;
                //printf("j: %dn",j);
            }
            if (i < pre.size()){
                st.push(new TreeNode(pre[i]));
                //printf("push %dn",pre[i]);
            }
        }
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!