题解 | #将满二叉树转换为求和树#

大模拟的解法，感觉没有必要

#include <iostream>
#include <cstring>

using namespace std;

 struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int N = 110;
const char* const DELIM = " ";

int preorder[N], inorder[N], sz;

inline TreeNode* buildTree(int i, int j, int n) {
  if (not n) return nullptr; 
  auto root = new TreeNode(preorder[i]);
  if (n == 1) return root;

  int k = j;
  while (inorder[k] != preorder[i]) ++k;
  int l = k - j;

  root->left  = buildTree(i + 1, j, l);
  root->right = buildTree(i + 1 + l, k + 1, n - 1 - l);
  return root;
}

inline void visit(TreeNode* node) {
  printf("%d ", (*node).val);
}

inline void traverse(TreeNode* root, void (*visit) (TreeNode*)) {
  if (not root) return;
  traverse(root->left, visit);
  visit(root);
  traverse(root->right, visit);
}

inline int DFS(TreeNode* root) {
  if (not root) return 0;
  const int ls = DFS(root->left); 
  const int rs = DFS(root->right); 
  int s = root->val + ls + rs;
  root->val = ls + rs;
  return s;
}

int main(int argc, char const *argv[]) {

  char s[1 << 10];
  fgets(s, 1024, stdin);

  int sz = 0;
  char* tok = strtok(s, DELIM);
  while (tok) {
    preorder[sz++] = stoi(string(tok));
    tok = strtok(NULL, DELIM);
  }

  fgets(s, 1024, stdin); sz = 0;
  tok = strtok(s, DELIM);
  while (tok) {
    inorder[sz++] = stoi(string(tok));
    tok = strtok(NULL, DELIM);
  }

  auto rt = buildTree(0, 0, sz);
  DFS(rt);
  traverse(rt, visit);
  return 0;
}