欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

pat 1086 Tree Traversals Again

程序员文章站 2022-07-08 18:33:55
...

思路 模拟遍历

用自己的思路就会出错……折磨死了。自己还是太菜了。

边遍历边建树

/*思路:建树*/
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
struct Node
{
    int data;
    Node *left;
    Node *right;

    Node() { left = right = NULL; }
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};

void insert(int data, int NodeData, Node *&root)
{
    if (root == NULL)
        return;

    if (root->data == NodeData)
    { /*这里把==写成了=*/
        if (root->left == NULL)
        {
            Node *nodeL = new Node(data);
            root->left = nodeL;
        }
        else
        {
            Node *nodeR = new Node(data);
            root->right = nodeR;
        }
        return;
    }

    insert(data, NodeData, root->left);
    insert(data, NodeData, root->right);
}

vector<int> pOrder;
void postOrder(Node *root)
{
    if (root == NULL)   return;
    postOrder(root->left);
    postOrder(root->right);
    pOrder.push_back(root->data);
}

int main()
{
    int N;  
    cin >> N;
    getchar();
    
    stack<int> st;

    string s;   
    getline(cin, s);
    
    Node *root = new Node(s[5] - '0');
    int RData = s[5] - '0';

    st.push(s[5] - '0');
    while (getline(cin, s))
    {
        if (s[1] == 'u')
        {
            st.push(s[5] - '0');
            insert(s[5] - '0', RData, root);
            RData = st.top();
        }
        else
        {
            RData = st.top();
            st.pop();
        }
    }
    postOrder(root);
    for (int i = 0; i < pOrder.size(); i++)
    {
        if (i != pOrder.size() - 1) cout << pOrder[i] << " ";
        else    cout << pOrder[i] << endl;
    }
    return 0;
}

pat 1086 Tree Traversals Again
换成了前序遍历和中序遍历推后序遍历的思路最后一个测试点依然答案错误

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node() { left = right = NULL; }
    Node(int data) { this->data = data; left = right = NULL; }
};
vector<int> preOrder;
vector<int> inOrder;
vector<int> postOrder;
Node* create(int preL, int preR, int inL, int inR) {
    if (preL > preR)    return NULL;
    Node* root = new Node(preOrder[preL]);
    
    int k;
    for (k = inL; k <= inR; k ++) if (inOrder[k] == root->data) break;
    
    int numLeft = k - inL;      //左子树的长度
    
    root->left =  create(preL + 1, preL + numLeft, inL, k - 1);     //创建左子树
    root->right = create(preL + numLeft + 1, preR, k + 1, inR);     //创建右子树
    
    return root;
}

void pOrder(Node* root) {
    if (root == NULL)   return ;
    pOrder(root->left);
    pOrder(root->right);
    postOrder.push_back(root->data);
}
 
int main() {
    int N;  cin >> N;   getchar();
    string s;
    stack<int> st;
    while (getline(cin, s)) {
        if (s[1] == 'u') {
            preOrder.push_back(s[5] - '0');
            st.push(s[5] - '0');
        }
        else {
            inOrder.push_back(st.top());
            st.pop();
        }
    }
    
    Node* root = create(0, N - 1, 0, N - 1);
    pOrder(root);
    for (int i = 0; i < postOrder.size(); i ++) {
        if (i != postOrder.size() - 1)  cout << postOrder[i] << " ";
        else cout << postOrder[i] << endl;
    }
    
    return 0;
}

问题解决了。当Push 后面的数多于两位时就会出现错误。如Push 32,只会把3加入

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node() { left = right = NULL; }
    Node(int data) { this->data = data; left = right = NULL; }
};
vector<int> preOrder;
vector<int> inOrder;
vector<int> postOrder;
Node* create(int preL, int preR, int inL, int inR) {
    if (preL > preR)    return NULL;
    Node* root = new Node(preOrder[preL]);
    
    int k;
    for (k = inL; k <= inR; k ++) if (inOrder[k] == root->data) break;
    
    int numLeft = k - inL;      //左子树的长度
    
    root->left =  create(preL + 1, preL + numLeft, inL, k - 1);     //创建左子树
    root->right = create(preL + numLeft + 1, preR, k + 1, inR);     //创建右子树
    
    return root;
}

void pOrder(Node* root) {
    if (root == NULL)   return ;
    pOrder(root->left);
    pOrder(root->right);
    postOrder.push_back(root->data);
}
 
int main() {
    int N, num;  cin >> N; 
    string s;
    stack<int> st;
    while (cin >> s) {
        if (s[1] == 'u') {
            cin >> num;
            preOrder.push_back(num);
            st.push(num);
        }
        else {
            inOrder.push_back(st.top());
            st.pop();
        }
    }
    
    Node* root = create(0, N - 1, 0, N - 1);
    pOrder(root);
    for (int i = 0; i < postOrder.size(); i ++) {
        if (i != postOrder.size() - 1)  cout << postOrder[i] << " ";
        else cout << postOrder[i] << endl;
    }
    
    return 0;
}
相关标签: 二叉树