正经题解-Gold King的二叉树遍历

#include <bits/stdc++.h>
using namespace std;

// 树节点结构体
struct TreeNode {
    int value, leftChild, rightChild;
};

int main() {
    int n;
    cin >> n;

    vector<TreeNode> tree(n + 1);
    vector<int> preOrder, stackSize;

    // 读取节点值
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].value;
    }

    // 构建二叉搜索树
    for (int i = 2; i <= n; i++) {
        int j = 1;
        while (true) {
            if (tree[j].value > tree[i].value) {
                if (!tree[j].leftChild) {
                    tree[j].leftChild = i;
                    break;
                } else {
                    j = tree[j].leftChild;
                }
            } else {
                if (!tree[j].rightChild) {
                    tree[j].rightChild = i;
                    break;
                } else {
                    j = tree[j].rightChild;
                }
            }
        }
    }

    stack<TreeNode> nodeStack;
    TreeNode currentNode = tree[1];

    // 非递归先序遍历
    while (!nodeStack.empty() || currentNode.value) {
        while (currentNode.value) {
            nodeStack.push(currentNode);
            preOrder.push_back(currentNode.value);
            stackSize.push_back(nodeStack.size());
            currentNode = tree[currentNode.leftChild];
        }
        currentNode = nodeStack.top();
        nodeStack.pop();
        currentNode = tree[currentNode.rightChild];
    }

    // 输出先序遍历结果
    for (auto value : preOrder) {
        printf("%5d", value);
    }

    cout << endl;

    // 输出每次当前遍历输出时，栈中元素个数
    for (auto size : stackSize) {
        printf("%5d", size);
    }

    return 0;
}