M24729: 括号嵌套树

dfs, stack, http://cs101.openjudge.cn/practice/24729/

思路：注意到树的构建与栈是一致的，用栈来辅助构建会很方便，非常简单，用时约15min

#include <iostream>  
#include <vector>  
#include <map>  
#include <string>  
#include <sstream>  
using namespace std;  
struct TreeNode  
{  
    char name;  
    vector<TreeNode*> children;  
    TreeNode(char c) : name(c) {}  
};  
class Solution   
{  
public:  
    TreeNode* root;  
    void getTree()  
    {  
        char c;  
        TreeNode* lastnode;  
        vector<TreeNode*> stack;  
        while (cin >> c)  
        {  
            if (c == ',')continue;  
            if (c == '(')  
                stack.push_back(lastnode);  
            else if (c == ')')  
                stack.pop_back();  
            else  
            {  
                TreeNode* node = new TreeNode(c);  
                if (stack.empty())  
                    root = node;  
                else  
                    stack.back()->children.push_back(node);  
                lastnode = node;  
            }  
        }     
    }  
    void printTree_1(TreeNode* node)  
    {  
        if (node == nullptr)return;  
        cout << node->name;  
        for (auto child : node->children)  
            printTree_1(child);  
    }  
    void printTree_2(TreeNode* node)  
    {  
        if (node == nullptr)return;  
        for (auto child : node->children)  
            printTree_2(child);  
        cout << node->name;  
    }  
};  
int main()   
{  
    Solution s;  
    s.getTree();  
    s.printTree_1(s.root);  
    cout << endl;  
    s.printTree_2(s.root);  
    return 0;  
}

​

思路：用栈解析括号表达式建树，再递归输出前序与后序序列。

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

struct Node {
    char val;
    vector<Node*> children;
    Node(char c) : val(c) {}
};

void preorder(Node* root) {
    if (!root) return;
    cout << root->val;
    for (auto child : root->children)
        preorder(child);
}

void postorder(Node* root) {
    if (!root) return;
    for (auto child : root->children)
        postorder(child);
    cout << root->val;
}

int main() {
    string s;
    cin >> s;
    stack<Node*> st;
    Node* root = nullptr;
    Node* last = nullptr;

    for (int i = 0; i < (int)s.size(); ++i) {
        char c = s[i];
        if (isupper(c)) { 
            Node* node = new Node(c);
            if (!st.empty())
                st.top()->children.push_back(node);
            else
                root = node;
            last = node;
        } else if (c == '(') {
            st.push(last);
        } else if (c == ')') {
            st.pop();
        } else if (c == ',') {
            continue;
        }
    }

    preorder(root);
    cout << "\n";
    postorder(root);
    cout << "\n";

    return 0;
}