Data-Structure/Exercise/Homework4/ab间路径.cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector<vector<int>> result; 
vector<int> leftt, rightt;

template <class T>
struct Node {
    T element;
    Node<T>* left;
    Node<T>* right;
    Node<T>* parent;
    
    Node(const T& e, Node<T>* p) : element(e), parent(p), left(nullptr), right(nullptr) {}
};

template <class T>
class BinTree {
public:
    Node<T>* root;
    int height;
    vector<T> arr;
        
    BinTree() : root(nullptr), height(0) {}
    BinTree(const vector<T>& arrs) : arr(arrs), height(0) {}
    void test() {
        for (auto x : arr) {
            cout << x << " ";
        }
    }
    Node<T>* returnroot() {
        return this->root;
    }
        
    Node<T>* build(int& index, Node<T>* parent) {
        if (index >= arr.size() || arr[index] == 0) {
            index++;
            return nullptr;
        }
        
        Node<T>* node = new Node<T>(arr[index], parent);
        index++;
        node->left = build(index, node);
        node->right = build(index, node);
        
        return node;
    }
        
    void buildTree() {
        int index = 0;
        this->root = build(index, nullptr);
    }
        
    //输出
    void preorder(Node<T>* node) {
        if (node == nullptr) return;
        
        cout << node->element << " ";
        preorder(node->left);
        preorder(node->right);
    }
    void inorder(Node<T>* node) {
        if (node == nullptr) return;

        inorder(node->left);
        cout << node->element << " ";
        //cout << ( node->parent == nullptr ? 0 : node->parent->element) << endl;
        inorder(node->right);
    }
    void postorder(Node<T>* node) {
        if (node == nullptr) return;
        
        postorder(node->left);
        postorder(node->right);
        cout << node->element << " ";
    }
    Node<T>* inorder2(Node<T>* node, const T& x) {
        if (node == nullptr) return nullptr;
        
        if (node->element == x) {
            return node;
        }
        
        Node<T>* leftResult = inorder2(node->left, x);
        if (leftResult != nullptr) {
            return leftResult;
        }
        
        Node<T>* rightResult = inorder2(node->right, x);
        return rightResult;
    }
    void findparent(const T& e) {
        auto x = inorder2(this->root, e);
        if (x == nullptr || x->parent == nullptr) cout << 0 << endl;
        else         cout << x->parent->element << endl;
    }
    void deletesub(Node<T>* node) {
        if (node == nullptr) return;
        deletesub(node->left);
        deletesub(node->right);
        delete node;
    }

    bool deletenode(const T& e) {
        auto x = inorder2(this->root, e);
        if (x == nullptr) return false;
        
        if (x == this->root) {
            deletesub(x);
            this->root = nullptr;
            return true;
        }
        
        if (x->parent->left == x) {
            x->parent->left = nullptr;
        } else {
            x->parent->right = nullptr;
        }
        deletesub(x);
        return true;
    }
    
    void searchpath(T a, T b) {
        Node<T>* na = inorder2(root, a);
        Node<T>* nb = inorder2(root, b);
        if (!na || !nb) { cout << 0 << endl << endl; return; }
        
        vector<Node<T>*> patha;
        Node<T>* cur = na;
        while (cur) {
            patha.push_back(cur);
            cur = cur->parent;
        }
        reverse(patha.begin(), patha.end());
        
        vector<Node<T>*> pathb;
        cur = nb;
        while (cur) {
            pathb.push_back(cur);
            cur = cur->parent;
        }
        reverse(pathb.begin(), pathb.end());

        int lena = patha.size(), lenb = pathb.size();
        int minlen = min(lena, lenb);
        
        int idx = 0;
        for (int i = 0; i < minlen; ++i) {
            if (patha[i] == pathb[i]) idx = i;
            else break;
        }
        
        vector<T> allpath;
        for (int j = lena - 1; j > idx; j--) {
            allpath.push_back(patha[j]->element);
        }
        allpath.push_back(patha[idx]->element);
        for (int j = idx + 1; j < lenb; j++) {
            allpath.push_back(pathb[j]->element);
        }
        
        int length = allpath.size() - 1;
        cout << length << endl;
        
        for (int i = 0; i < allpath.size(); ++i) {
            cout << allpath[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    int x = 0;
    vector<int> arr;
    string line;
    getline(cin, line);
    stringstream ss(line);
    int num;

    while (ss >> num) {
        arr.push_back(num);
    }
    BinTree<int> tree(arr);
    tree.buildTree();

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        tree.searchpath(a, b);
    }
    
    
    return 0;
}