已知二叉排序树用二叉链表存储，结点的关键字为正整数。从键盘输入结点的关键字（以0表示结束）建立一棵二叉排序树，并输出其后序遍历序列。

输入示例：
40 20 60 70 0

输出示例：
20 70 60 40

#include <iostream>
using namespace std;

struct TreeNode {
  TreeNode *lchild, *rchild;
  int val;
  TreeNode(int val) : lchild(nullptr), rchild(nullptr), val(val) {}
};

TreeNode *root = nullptr;
int flag = 0;

void insertNode(int val) {
  if (!root) {
    root = new TreeNode(val);
    return;
  }
  TreeNode *t = root;
//   pre用于上一个结点的指针
  TreeNode *pre;
  while (t) {
    pre = t;
    if (val >= t->val)
      t = t->rchild;
    else
      t = t->lchild;
  }
  if (val >= pre->val)
    pre->rchild = new TreeNode(val);
  else
    pre->lchild = new TreeNode(val);
}

// 进行后续遍历
void postOrder(TreeNode *t) {
  if (!t) return;
  postOrder(t->lchild);
  postOrder(t->rchild);
  if (flag) cout << " ";
  cout << t->val;
  flag = 1;
}

int main() {
  int num;
  while (cin >> num) {
    if (num == 0) break;
    insertNode(num);
  }
  postOrder(root);
  return 0;
}