再次树遍历

• 第一次加入的一定是根

• 对于所有的 push ，如果上一个是 push ，说明当前这个点是上一个点的左儿子。如果上一个是 pop ，说明当前这个点是上一个点的右儿子。

• 这道题也可以把 push 相成先序遍历， pop 是中序遍历。

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 35;

int n;
int l[N], r[N];
int root;

#define printf

void dfs(int u)
{
  if (l[u]) dfs(l[u]);
  if (r[u]) dfs(r[u]);

  if (u == root) cout << root;
  else cout << u << " ";
}

int main()
{
  cin >> n;
  int last = 0;
  stack<int> s;
  int type = 0; // 0表示上一个push，1表示上一个pop
  for (int i = 0; i < n << 1; i ++ )
  {
      string op;
      cin >> op;
      if (op == "Push")
      {
          int x;
          cin >> x;
          if (!last) root = x;
          else
          {
              if (type == 0) 
              {
                  l[last] = x;
                  printf("l[%d] = %d\n", last, x);
              }
              else 
              {
                  r[last] = x;
                  printf("r[%d] = %d\n", last, x);
              }
          }
          last = x;
          s.push(x);
          type = 0;
      }
      else
      {
          type = 1;
          last = s.top();
          s.pop();
      }
  }

  dfs(root);

  return 0;
}