二叉树建树与遍历的基本功

#include <iostream>
#include <sstream>

using namespace std;
string extends;

struct TreeNode {
  char val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(' '), left(nullptr), right(nullptr) {};
  TreeNode(char _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(char _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

// 从字符串中反序列化出一颗二叉树
TreeNode* deserialize(istringstream& in) {
  char val;
  in >> val;
  if (val == '.') return nullptr;

  auto root = new TreeNode(val);
  root->left  = deserialize(in);
  root->right = deserialize(in);
  return root;
}

void inOrder(TreeNode* root) {
  if (!root) return;
  inOrder(root->left);
  printf("%c", root->val);
  inOrder(root->right);
}

void postOrder(TreeNode* root) {
  if (!root) return;
  postOrder(root->left);
  postOrder(root->right);
  printf("%c", root->val);
}

int main(void) {
  cin >> extends;
  ostringstream out;
  for (const char c : extends)
    out << c << ' ';

  istringstream in(out.str());
  auto root = deserialize(in);

  inOrder(root);
  printf("\n");
  postOrder(root);
  return 0;
}