题目来源

• 华为机试：二叉树中序遍历

题目描述

题目解析

思路

class Solution{struct TreeNode{char ch;TreeNode *left;TreeNode *right;public:TreeNode(char ch) : ch(ch){}};std::deque<TreeNode *> deque;bool isNode(char ch){return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');};// 返回下一个要看的位置int process(std::string &str, int start){int i = start;while (i < str.size() && str[i] != '}') {if(isNode(str[i])){  // {a}, a, a{}, {a.}deque.push_back(new TreeNode(str[i]));  // {f}if(i + 1 < str.size() && str[i + 1] == '}'){  deque.push_back(NULL);}i = i + 1;}else if(str[i] == '{'){   // {f}i = process(str, i + 1);}else {if(str[i - 1] == '{' && str[i + 1] == '}'){deque.push_back(NULL);deque.push_back(NULL);i = i + 1;}else if(str[i - 1] == '{'){  // {.a}deque.push_back(NULL);deque.push_back(new TreeNode(str[i + 1]));i = i + 2;}else if(str[i + 1] == '}'){  // {a.}deque.push_back(NULL);i = i + 1;}else{  // d,edeque.push_back(new TreeNode(str[i + 1]));i = i + 2;}}}if(deque.size() >= 3){auto right = deque.back(); deque.pop_back();auto left = deque.back(); deque.pop_back();deque.back()->right = right;deque.back()->left = left;}return i + 1;}
public:TreeNode *genereTree(std::string &str){if(str.empty()){return NULL;}process(str, 0);return deque.front();  //至少会含有一个}void inorderTraval(TreeNode *root,  std::string &ans){if(root == nullptr){return ;}inorderTraval(root->left, ans);ans.push_back(root->ch);inorderTraval(root->right, ans);}
};

int main(){std::string line = "a{b{d,e{g,h{,I}}},c{f}}";while (getline(cin, line)){Solution a;auto root = a.genereTree(line);std::string order;a.inorderTraval(root, order);std::cout << order << "\n";}return 0;
}