cpp-handwritten-coding-public/problems/binary_tree/include/binary_tree.h at main · Excaliiiibur/cpp-handwritten-coding-public · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#pragma once

#include <optional>
#include <vector>

class BinaryTree {
private:
    struct Node {
        int value;
        Node* left;
        Node* right;

        explicit Node(int v) : value(v), left(nullptr), right(nullptr) {}
    };

    Node* root;

    static Node* build(const std::vector<int>& preorder,
                       int preL,
                       int preR,
                       const std::vector<int>& inorder,
                       int inL,
                       int inR);
    static void free_tree(Node* node);
    static void collect_pre(Node* node, std::vector<int>& out);
    static void collect_in(Node* node, std::vector<int>& out);
    static void collect_post(Node* node, std::vector<int>& out);

public:
    BinaryTree();
    explicit BinaryTree(const std::vector<std::optional<int>>& level);
    BinaryTree(const std::vector<int>& preorder, const std::vector<int>& inorder);
    ~BinaryTree();

    BinaryTree(const BinaryTree&) = delete;
    BinaryTree& operator=(const BinaryTree&) = delete;

    bool empty() const;
    void clear();

    std::vector<int> preorder() const;
    std::vector<int> inorder() const;
    std::vector<int> postorder() const;
    std::vector<int> level_order() const;
};