// 二叉树的链表结构
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 10000; // 用于数组实现的队列或栈

template <class T>
struct BiNode
{
    T data;
    BiNode<T> *lchild, *rchild;

    // 构造函数，方便初始化
    BiNode(T val) : data(val), lchild(nullptr), rchild(nullptr) {}
    BiNode(T val, BiNode<T> *l, BiNode<T> *r) : data(val), lchild(l), rchild(r) {}
};

template <class T>
class BiTree
{
public:
    // 默认构造函数
    BiTree() { root = nullptr; }

    // 析构函数
    ~BiTree()
    {
        Release(root);
    }

    // 核心功能接口 (以 root 为参数，方便外部调用或对子树操作)
    void PreOrder_Recursive(BiNode<T> *R);  // 递归先序遍历
    void InOrder_Recursive(BiNode<T> *R);   // 递归中序遍历
    void PostOrder_Recursive(BiNode<T> *R); // 递归后序遍历

    void PreOrder_IterativeStack(BiNode<T> *R);    // 迭代先序遍历（使用std::stack）
    void PreOrder_IterativePtrArray(BiNode<T> *R); // 迭代先序遍历（使用指针数组模拟栈）
    void InOrder_Iterative(BiNode<T> *R);          // 迭代中序遍历
    void PostOrder_Iterative(BiNode<T> *R);        // 迭代后序遍历

    void LevelOrder_StdQueue(BiNode<T> *R);   // 层序遍历（使用std::queue）
    void LevelOrder_ArrayQueue(BiNode<T> *R); // 层序遍历（使用数组模拟队列）

    int GetDepth_Recursive(BiNode<T> *R); // 递归获取深度
    int GetDepth_Iterative(BiNode<T> *R); // 迭代获取深度

    int Count(BiNode<T> *R);               // 统计结点数（递归）
    int LeafCount_Recursive(BiNode<T> *R); // 递归统计叶子数
    int LeafCount_Iterative(BiNode<T> *R); // 迭代统计叶子数

    void CopyTree(BiNode<T> *R, BiNode<T> *&T2);   // 拷贝树
    bool Path(BiNode<T> *R, T e, vector<T> &path); // 查找路径

    // 不同的树创建方法
    // 从完全二叉树的数组表示创建（1-based index, 0代表空）
    void CreateFromCompleteArray_Recursive(BiNode<T> *&R_ref, T data[], int i, int array_size);
    // 从完全二叉树的数组表示创建（1-based index, 0代表空）
    void CreateFromCompleteArray_Iterative(BiNode<T> *&R_ref, T data[], int i, int array_size);
    // 从数组（0-based index) 迭代构建完全二叉树 (nullval 代表空)
    void CreateFromCompleteArray_BFS_Iterative(BiNode<T> *&R_ref, T data[], int n, const T &nullval);

    // 从先序和中序遍历序列构建
    void CreateFromPreInOrder(BiNode<T> *&R_ref, T PreData[], T InData[], int l1, int h1, int l2, int h2);
    // 从中序和后序遍历序列构建
    void CreateFromInPostOrder(BiNode<T> *&R_ref, T InData[], T PostData[], int l1, int h1, int l2, int h2);

    // 提供一个公共的获取根节点的方法，或者让一些方法直接操作 root
    BiNode<T> *getRoot() const { return root; }
    void setRoot(BiNode<T> *newRoot) { root = newRoot; }

private:
    BiNode<T> *root; // 树的根节点

    // 辅助释放函数
    void Release(BiNode<T> *&R);
};

// =====================================================================
// 实现部分
// =====================================================================

// 通过完全二叉树的数组表示（1-based index）递归构建 (0表示空节点)
template <class T>
void BiTree<T>::CreateFromCompleteArray_Recursive(BiNode<T> *&R_ref, T data[], int i, int array_size)
{
    // i 是 1-based 索引，array_size 是数组的实际元素个数
    // data 数组是 0-based 索引，所以 data[i-1]
    if (i > array_size || data[i - 1] == 0)
    { // 超过数组范围或遇到空值
        R_ref = nullptr;
        return;
    }

    R_ref = new BiNode<T>(data[i - 1]);
    CreateFromCompleteArray_Recursive(R_ref->lchild, data, 2 * i, array_size);
    CreateFromCompleteArray_Recursive(R_ref->rchild, data, 2 * i + 1, array_size);

    // 如果这是第一次调用，并且是建立整个树，设置类成员root
    if (i == 1)
    { // 仅当根节点通过此方法创建时设置
        root = R_ref;
    }
}

// 通过完全二叉树的数组表示（1-based index）非递归构建 (0表示空节点)
template <class T>
void BiTree<T>::CreateFromCompleteArray_Iterative(BiNode<T> *&R_ref, T data[], int i, int array_size)
{
    // 这段代码是基于你原始代码的非递归 Create 实现
    stack<pair<BiNode<T> **, int>> st;
    st.push({&R_ref, i}); // 将根节点的指针的地址和其索引压栈

    // 用于处理第一次设置 root 的情况
    BiNode<T> **current_root_ptr = &R_ref;
    bool root_set = false;

    while (!st.empty())
    {
        auto p = st.top();
        st.pop();
        BiNode<T> **pp = p.first; // 当前要创建节点的指针的地址
        int idx = p.second;       // 当前节点的 1-based 索引

        if (idx > array_size || data[idx - 1] == 0) // 超过数组范围或空节点
        {
            *pp = nullptr; // 将指针设为 nullptr
        }
        else
        {
            BiNode<T> *node = new BiNode<T>(data[idx - 1]);
            *pp = node; // 将新创建的节点赋值给对应的指针

            if (!root_set && pp == current_root_ptr)
            { // 确保只设置一次类成员root
                root = node;
                root_set = true;
            }

            // 先压入右孩子，再压入左孩子（栈是LIFO，保证左子树先被处理）
            st.push({&node->rchild, 2 * idx + 1});
            st.push({&node->lchild, 2 * idx});
        }
    }
}

// 从数组（0-based index) 迭代构建完全二叉树 (nullval 代表空) - 类似于BFS
template <class T>
void BiTree<T>::CreateFromCompleteArray_BFS_Iterative(BiNode<T> *&R_ref, T data[], int n, const T &nullval)
{
    if (n <= 0 || data[0] == nullval)
    {
        R_ref = nullptr; // 确保传入的引用也设为nullptr
        root = nullptr;
        return;
    }

    R_ref = new BiNode<T>(data[0]);
    root = R_ref; // 设置类成员root

    queue<pair<BiNode<T> *, int>> q;
    q.push({R_ref, 0}); // 存储节点地址和其在数组中的 0-based 索引

    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        BiNode<T> *node = cur.first; // 当前父节点
        int i = cur.second;          // 当前父节点在数组中的索引

        // 创建左孩子
        int li = 2 * i + 1;
        if (li < n && data[li] != nullval)
        {
            BiNode<T> *left = new BiNode<T>(data[li]);
            node->lchild = left;
            q.push({left, li});
        }
        else
        {
            node->lchild = nullptr;
        }

        // 创建右孩子
        int ri = 2 * i + 2;
        if (ri < n && data[ri] != nullval)
        {
            BiNode<T> *right = new BiNode<T>(data[ri]);
            node->rchild = right;
            q.push({right, ri});
        }
        else
        {
            node->rchild = nullptr;
        }
    }
}

// 辅助释放函数
template <class T>
void BiTree<T>::Release(BiNode<T> *&R)
{
    if (R != nullptr)
    { // 只有当节点非空时才递归释放
        Release(R->lchild);
        Release(R->rchild);
        delete R;
        R = nullptr; // 将指针置为nullptr，防止悬空指针
    }
}

// 递归先序遍历
template <class T>
void BiTree<T>::PreOrder_Recursive(BiNode<T> *R)
{
    if (R != nullptr)
    {
        cout << R->data << " ";
        PreOrder_Recursive(R->lchild);
        PreOrder_Recursive(R->rchild);
    }
}

// 递归中序遍历
template <class T>
void BiTree<T>::InOrder_Recursive(BiNode<T> *R)
{
    if (R != nullptr)
    {
        InOrder_Recursive(R->lchild); // 注意这里应该调用 InOrder_Recursive 而不是 PreOrder
        cout << R->data << " ";
        InOrder_Recursive(R->rchild); // 注意这里应该调用 InOrder_Recursive 而不是 PreOrder
    }
}

// 递归后序遍历
template <class T>
void BiTree<T>::PostOrder_Recursive(BiNode<T> *R)
{
    if (R != nullptr)
    {
        PostOrder_Recursive(R->lchild); // 注意这里应该调用 PostOrder_Recursive 而不是 PreOrder
        PostOrder_Recursive(R->rchild); // 注意这里应该调用 PostOrder_Recursive 而不是 PreOrder
        cout << R->data << " ";
    }
}

// 层序遍历 (使用std::queue)
template <class T>
void BiTree<T>::LevelOrder_StdQueue(BiNode<T> *R)
{
    queue<BiNode<T> *> q;
    if (R != nullptr)
    {
        q.push(R);
    }
    while (!q.empty())
    {
        BiNode<T> *node = q.front();
        q.pop();
        cout << node->data << " ";
        if (node->lchild != nullptr)
            q.push(node->lchild);
        // 原代码 q.front().rchild 是语法错误，已修正
        if (node->rchild != nullptr)
            q.push(node->rchild);
    }
}

// 层序遍历 (使用数组模拟队列实现)
template <class T>
void BiTree<T>::LevelOrder_ArrayQueue(BiNode<T> *R)
{
    BiNode<T> *que[MaxSize]; // 普通数组模拟队列
    int front = 0;           // 队头指针
    int rear = 0;            // 队尾指针（指向下一个可插入位置）

    if (R != nullptr)
    {
        que[rear++] = R; // 入队
    }

    while (front < rear)
    {                                   // 队列不为空
        BiNode<T> *node = que[front++]; // 出队
        if (node != nullptr)
        { // 通常情况下，队列中不会有 nullptr，但为了保险
            cout << node->data << " ";

            if (node->lchild != nullptr)
            {
                que[rear++] = node->lchild; // 左孩子入队
            }
            if (node->rchild != nullptr)
            {
                que[rear++] = node->rchild; // 右孩子入队
            }
        }
    }
}

// 统计结点数（递归）
template <class T>
int BiTree<T>::Count(BiNode<T> *R)
{
    if (R == nullptr)
        return 0;
    else
    {
        int m = Count(R->lchild);
        int n = Count(R->rchild);
        return m + n + 1;
    }
}

// 统计叶子结点数（递归）
template <class T>
int BiTree<T>::LeafCount_Recursive(BiNode<T> *R)
{
    if (R == nullptr)
        return 0;
    if (R->lchild == nullptr && R->rchild == nullptr) // 这是一个叶子节点
        return 1;
    else
    {
        int m = LeafCount_Recursive(R->lchild);
        int n = LeafCount_Recursive(R->rchild);
        return m + n;
    }
}

// 统计叶子结点数（迭代 - BFS实现）
template <class T>
int BiTree<T>::LeafCount_Iterative(BiNode<T> *R)
{
    if (R == nullptr)
        return 0;
    int cnt = 0;
    queue<BiNode<T> *> q;
    q.push(R);
    while (!q.empty())
    {
        BiNode<T> *node = q.front();
        q.pop();
        if (!node->lchild && !node->rchild) // 是叶子节点
            ++cnt;
        if (node->lchild)
            q.push(node->lchild);
        if (node->rchild)
            q.push(node->rchild);
    }
    return cnt;
}

// 获取树的深度（递归）
template <class T>
int BiTree<T>::GetDepth_Recursive(BiNode<T> *R)
{
    if (R == nullptr)
        return 0;
    return std::max(GetDepth_Recursive(R->lchild), GetDepth_Recursive(R->rchild)) + 1; // 使用std::max
}

// 获取树的深度（迭代 - BFS实现）
template <class T>
int BiTree<T>::GetDepth_Iterative(BiNode<T> *R)
{
    if (R == nullptr)
        return 0;
    queue<BiNode<T> *> q;
    q.push(R);
    int depth = 0;
    while (!q.empty())
    {
        int sz = q.size(); // 当前层的节点数量
        ++depth;           // 深度加1
        for (int i = 0; i < sz; ++i)
        {
            BiNode<T> *node = q.front();
            q.pop();
            if (node->lchild)
                q.push(node->lchild);
            if (node->rchild)
                q.push(node->rchild);
        }
    }
    return depth;
}

// 先序遍历 (迭代 - 使用std::stack)
template <class T>
void BiTree<T>::PreOrder_IterativeStack(BiNode<T> *R)
{
    if (R == nullptr)
        return;
    stack<BiNode<T> *> s;
    s.push(R);
    while (!s.empty())
    {
        BiNode<T> *node = s.top();
        s.pop();
        cout << node->data << " ";
        // 先压右孩子，再压左孩子，这样出栈时左孩子先被处理
        if (node->rchild)
            s.push(node->rchild);
        if (node->lchild)
            s.push(node->lchild);
    }
}

// 先序遍历 (迭代 - 使用指针数组模拟栈)
template <class T>
void BiTree<T>::PreOrder_IterativePtrArray(BiNode<T> *R)
{
    BiNode<T> *S[MaxSize]; // 栈（指针数组）
    int top = -1;
    BiNode<T> *curr = R; // 当前处理的节点
    while (top != -1 || curr != nullptr)
    {
        while (curr != nullptr)
        {
            cout << curr->data << " "; // 访问根节点
            S[++top] = curr;           // 压入栈
            curr = curr->lchild;       // 转向左孩子
        }
        if (top != -1)
        {
            curr = S[top--];     // 弹出栈顶节点
            curr = curr->rchild; // 转向右孩子
        }
    }
}

// 中序遍历 (迭代 - 使用std::stack)
template <class T>
void BiTree<T>::InOrder_Iterative(BiNode<T> *R)
{
    stack<BiNode<T> *> s;
    BiNode<T> *node = R;
    while (node != nullptr || !s.empty())
    {
        while (node != nullptr)
        { // 一路向左，并将节点压栈
            s.push(node);
            node = node->lchild;
        }
        if (!s.empty())
        {                   // 栈不为空，说明有父节点或已访问完的左子树
            node = s.top(); // 弹出栈顶节点（是当前子树的根或左子树的右边界）
            s.pop();
            cout << node->data << " "; // 访问根节点
            node = node->rchild;       // 转向右子树
        }
    }
}

// 后序遍历 (迭代 - 双栈法)
template <class T>
void BiTree<T>::PostOrder_Iterative(BiNode<T> *R)
{
    stack<BiNode<T> *> s1, s2; // s1 为工作栈，s2 用于反转确定后序顺序
    if (R != nullptr)
        s1.push(R);
    while (!s1.empty())
    {
        BiNode<T> *node = s1.top();
        s1.pop();
        s2.push(node); // 将节点压入辅助栈
        // 先压左孩子，再压右孩子，这样在s2中右孩子会在左孩子之后
        if (node->lchild != nullptr)
            s1.push(node->lchild);
        if (node->rchild != nullptr)
            s1.push(node->rchild);
    }
    while (!s2.empty())
    { // 辅助栈逆序弹出即为后序遍历结果
        cout << s2.top()->data << " ";
        s2.pop();
    }
}

// 根据先序和中序遍历序列构建二叉树
// PreData: 先序遍历序列, InData: 中序遍历序列
// l1, h1: 先序序列的起始和结束索引
// l2, h2: 中序序列的起始和结束索引
template <class T>
void BiTree<T>::CreateFromPreInOrder(BiNode<T> *&R_ref, T PreData[], T InData[], int l1, int h1, int l2, int h2)
{
    if (l1 > h1 || l2 > h2)
    { // 区间无效，空树
        R_ref = nullptr;
        return;
    }

    R_ref = new BiNode<T>(PreData[l1]); // 先序序列的第一个元素是根节点

    // 找到根节点在中序序列中的位置
    int k;
    for (k = l2; k <= h2; k++)
    {
        if (InData[k] == PreData[l1])
            break;
    }
    // 如果没有找到，说明序列有误，这里简单处理，实际应用中可能需要抛出异常
    if (k > h2)
    {
        // 错误处理，例如：
        // delete R_ref;
        // R_ref = nullptr;
        // return;
        // 假设这里数据始终合法
    }

    int numLeft = k - l2; // 左子树的节点数量

    // 递归构建左子树
    CreateFromPreInOrder(R_ref->lchild, PreData, InData, l1 + 1, l1 + numLeft, l2, k - 1);
    // 递归构建右子树
    CreateFromPreInOrder(R_ref->rchild, PreData, InData, l1 + numLeft + 1, h1, k + 1, h2);

    // 如果是第一次调用，且是构建整个树，设置类成员root
    if (l1 == 0 && h1 == (sizeof(PreData) / sizeof(PreData[0]) - 1) && l2 == 0 && h2 == (sizeof(InData) / sizeof(InData[0]) - 1))
    {
        root = R_ref;
    }
    // 注意: 在main函数中调用时，需要将root设置为返回值
    // e.g. biTree.setRoot(R_ref);
}

// 根据中序和后序遍历序列构建二叉树
// InData: 中序遍历序列, PostData: 后序遍历序列
// l1, h1: 中序序列的起始和结束索引
// l2, h2: 后序序列的起始和结束索引
template <class T>
void BiTree<T>::CreateFromInPostOrder(BiNode<T> *&R_ref, T InData[], T PostData[], int l1, int h1, int l2, int h2)
{
    if (l1 > h1 || l2 > h2)
    { // 区间无效，空树
        R_ref = nullptr;
        return;
    }

    R_ref = new BiNode<T>(PostData[h2]); // 后序序列的最后一个元素是根节点

    // 找到根节点在中序序列中的位置
    int k;
    for (k = l1; k <= h1; k++)
    {
        if (InData[k] == PostData[h2])
            break;
    }
    // 如果没有找到，这里简单处理
    if (k > h1)
    {
        // 错误处理
    }

    int numLeft = k - l1; // 左子树的节点数量

    // 递归构建左子树
    // 中序：[l1, k-1], 后序：[l2, l2 + numLeft - 1]
    CreateFromInPostOrder(R_ref->lchild, InData, PostData, l1, k - 1, l2, l2 + numLeft - 1);
    // 递归构建右子树
    // 中序：[k+1, h1], 后序：[l2 + numLeft, h2 - 1]
    CreateFromInPostOrder(R_ref->rchild, InData, PostData, k + 1, h1, l2 + numLeft, h2 - 1);

    // 如果是第一次调用，且是构建整个树，设置类成员root
    if (l1 == 0 && h1 == (sizeof(InData) / sizeof(InData[0]) - 1) && l2 == 0 && h2 == (sizeof(PostData) / sizeof(PostData[0]) - 1))
    {
        root = R_ref;
    }
    // 注意: 在main函数中调用时，需要将root设置为返回值
    // e.g. biTree.setRoot(R_ref);
}

// 拷贝二叉树
template <class T>
void BiTree<T>::CopyTree(BiNode<T> *R, BiNode<T> *&T2)
{
    if (R == nullptr)
    {
        T2 = nullptr;
    }
    else
    {
        T2 = new BiNode<T>(R->data);
        CopyTree(R->lchild, T2->lchild);
        CopyTree(R->rchild, T2->rchild);
    }
}

// 查找从根到目标元素的路径
template <class T>
bool BiTree<T>::Path(BiNode<T> *R, T e, vector<T> &path)
{
    if (R == nullptr)
        return false;

    path.push_back(R->data); // 将当前节点加入路径

    if (R->data == e) // 找到目标元素
        return true;

    // 递归查找左子树或右子树
    if (Path(R->lchild, e, path) || Path(R->rchild, e, path))
        return true;

    path.pop_back(); // 如果当前节点不是目标，且它的子树中也找不到，则从路径中移除
    return false;
}

/*
// 示例使用 (需要自行添加 main 函数)
int main() {
    BiTree<int> tree;

    // 1. 从完全二叉树数组创建 (递归)
    // 假定 0 表示空节点
    // tree.CreateFromCompleteArray_Recursive(tree.getRoot(), data_array, 1, array_len);
    // 例如: int data1[] = {1, 2, 3, 4, 5, 0, 7}; // 1-based indexing, len = 7
    // BiNode<int>* r1 = nullptr;
    // tree.CreateFromCompleteArray_Recursive(r1, data1, 1, 7);
    // tree.setRoot(r1);

    // 2. 从完全二叉树数组创建 (迭代)
    // BiNode<int>* r2 = nullptr;
    // tree.CreateFromCompleteArray_Iterative(r2, data1, 1, 7);
    // tree.setRoot(r2);

    // 3. 从数组（0-based index) BFS 迭代创建
    // int data_bfs[] = {1, 2, 3, 4, 5, 0, 7}; // 0-based indexing, size = 7, 0代表空
    // BiNode<int>* r3 = nullptr;
    // tree.CreateFromCompleteArray_BFS_Iterative(r3, data_bfs, 7, 0); // 0是nullval
    // tree.setRoot(r3);

    // 4. 从先序和中序创建
    // int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    // int inorder[] = {4, 2, 5, 1, 6, 3, 7};
    // int n_pre_in = sizeof(preorder) / sizeof(preorder[0]);
    // BiNode<int>* r4 = nullptr;
    // tree.CreateFromPreInOrder(r4, preorder, inorder, 0, n_pre_in - 1, 0, n_pre_in - 1);
    // tree.setRoot(r4);


    // ... 调用各种遍历和统计函数 ...
    // cout << "PreOrder (Recursive): ";
    // tree.PreOrder_Recursive(tree.getRoot());
    // cout << endl;

    // cout << "InOrder (Iterative): ";
    // tree.InOrder_Iterative(tree.getRoot());
    // cout << endl;

    // cout << "Node Count: " << tree.Count(tree.getRoot()) << endl;
    // cout << "Depth (Iterative): " << tree.GetDepth_Iterative(tree.getRoot()) << endl;

    return 0;
}
*/