binary_tree.cpp

#include "binary_tree.h"

#include <queue>
#include <stdexcept>

BinaryTree::BinaryTree() : root(nullptr) {}

BinaryTree::BinaryTree(const std::vector<std::optional<int>>& level)
    : root(nullptr) {
    if (level.empty() || !level[0].has_value()) {
        return;
    }

    root = new Node(*level[0]);
    std::queue<Node*> q;
    q.push(root);

    std::size_t i = 1;
    while (!q.empty() && i < level.size()) {
        Node* cur = q.front();
        q.pop();

        if (i < level.size() && level[i].has_value()) {
            cur->left = new Node(*level[i]);
            q.push(cur->left);
        }
        ++i;

        if (i < level.size() && level[i].has_value()) {
            cur->right = new Node(*level[i]);
            q.push(cur->right);
        }
        ++i;
    }
}

BinaryTree::BinaryTree(const std::vector<int>& preorder,
                       const std::vector<int>& inorder)
    : root(nullptr) {
    if (preorder.size() != inorder.size()) {
        throw std::invalid_argument("preorder and inorder size mismatch");
    }

    if (!preorder.empty()) {
        root = build(preorder,
                     0,
                     static_cast<int>(preorder.size()) - 1,
                     inorder,
                     0,
                     static_cast<int>(inorder.size()) - 1);
    }
}

BinaryTree::~BinaryTree() {
    clear();
}

BinaryTree::Node* BinaryTree::build(const std::vector<int>& preorder,
                                    int preL,
                                    int preR,
                                    const std::vector<int>& inorder,
                                    int inL,
                                    int inR) {
    if (preL > preR) {
        return nullptr;
    }

    int rootValue = preorder[preL];
    int rootPos = inL;
    while (rootPos <= inR && inorder[rootPos] != rootValue) {
        ++rootPos;
    }

    if (rootPos > inR) {
        throw std::invalid_argument("invalid preorder/inorder sequence");
    }

    // 前序第一个是根；中序里根左边的长度就是左子树大小。
    int leftLen = rootPos - inL;
    Node* node = new Node(rootValue);
    node->left = build(preorder,
                       preL + 1,
                       preL + leftLen,
                       inorder,
                       inL,
                       rootPos - 1);
    node->right = build(preorder,
                        preL + leftLen + 1,
                        preR,
                        inorder,
                        rootPos + 1,
                        inR);
    return node;
}

void BinaryTree::free_tree(Node* node) {
    if (node == nullptr) {
        return;
    }

    free_tree(node->left);
    free_tree(node->right);
    delete node;
}

void BinaryTree::collect_pre(Node* node, std::vector<int>& out) {
    if (node == nullptr) {
        return;
    }

    out.push_back(node->value);
    collect_pre(node->left, out);
    collect_pre(node->right, out);
}

void BinaryTree::collect_in(Node* node, std::vector<int>& out) {
    if (node == nullptr) {
        return;
    }

    collect_in(node->left, out);
    out.push_back(node->value);
    collect_in(node->right, out);
}

void BinaryTree::collect_post(Node* node, std::vector<int>& out) {
    if (node == nullptr) {
        return;
    }

    collect_post(node->left, out);
    collect_post(node->right, out);
    out.push_back(node->value);
}

bool BinaryTree::empty() const {
    return root == nullptr;
}

void BinaryTree::clear() {
    free_tree(root);
    root = nullptr;
}

std::vector<int> BinaryTree::preorder() const {
    std::vector<int> out;
    collect_pre(root, out);
    return out;
}

std::vector<int> BinaryTree::inorder() const {
    std::vector<int> out;
    collect_in(root, out);
    return out;
}

std::vector<int> BinaryTree::postorder() const {
    std::vector<int> out;
    collect_post(root, out);
    return out;
}

std::vector<int> BinaryTree::level_order() const {
    std::vector<int> out;
    if (root == nullptr) {
        return out;
    }

    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();

        out.push_back(cur->value);
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }

    return out;
}