AcWing 1260. 二叉树输出
原题链接
简单
作者:
王小强
,
2021-02-09 14:24:51
,
所有人可见
,
阅读 674
全球首发 (完全根据题意模拟!)
#include <iostream>
#include <algorithm>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
int length;
TreeNode(char _val) : TreeNode(_val, 0) {};
TreeNode(char _val, int _length) : val(_val), length(_length), left(nullptr), right(nullptr) {};
};
string preorder, inorder;
TreeNode* buildTree(const string& preorder, const string& inorder) {
function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
if (n <= 0) return (TreeNode*) nullptr;
if (n == 1) return new TreeNode(preorder[i]);
int k = j;
while (inorder[k] != preorder[i]) ++k;
const int l = k - j; // l == 左子树的长度 ...
auto root = new TreeNode(inorder[k]);
root->left = construct(i + 1, j, l);
root->right = construct(i + 1 + l, k + 1, n - l - 1);
return root;
};
return construct(0, 0, preorder.size());
}
int postOrder(TreeNode* root) {
if (!root) return 0;
if (root->left == root->right) { // leaf node
root->length = 1;
return 1;
}
const int l = postOrder(root->left);
const int r = postOrder(root->right);
root->length = l + r;
return l + r;
}
void preOrder(TreeNode* root) {
if (!root) return;
int l = root->length;
while (l--) printf("%c", root->val);
printf("\n");
preOrder(root->left);
preOrder(root->right);
}
int main(void) {
// input
cin >> preorder >> inorder;
// process
auto root = buildTree(preorder, inorder);
postOrder(root);
// output
preOrder(root);
return 0;
}
####include[HTML_REMOVED]
###using namespace std;
###int num[26];
###int DFS(string pr,string mi){
if(!pr.size())return 0;
if(pr.size()==1){
num[pr[0]-‘A’]=1;
return 1;
}
bool right=0;
string ple=”“,pri=”“,mle=”“,mri=”“;
for(int i=0;i[HTML_REMOVED]>pre>>mid;
int i=DFS(pre,mid);
for(int i=0;i<pre.size();i){
for(int j=0;j<num[pre[i]-‘A’];j)cout<<pre[i];
cout<<endl;
}
return 0;
}
这样可以吗
代码格式怎么搞 我不会