Untitled
unknown
plain_text
4 years ago
5.3 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; string s; long long int pos, total, num; int ans, MaxSum; typedef struct Node { Node *left, *right; int data; }node; node* makenode(int a, int negative){ node* newnode = new node; if(negative == 1) newnode->data = -a; else newnode->data = a; total += newnode->data; newnode->left = newnode->right = NULL; return newnode; } node* buildTree(){ node *tmp = NULL; int val; if(s[pos] == '('){ pos++; int negative; if(s[pos] == '-'){ negative = 1; pos++; val = s[pos]-'0'; pos++; while(s[pos] >= '0' && s[pos] <='9'){ val = val*10+s[pos]-'0'; pos++; } tmp = makenode(val, negative); tmp->left = buildTree(); pos++; tmp->right = buildTree(); pos++; } else if(s[pos] >= '0' && s[pos] <='9'){ negative = 0; val = s[pos]-'0'; pos++; while(s[pos] >= '0' && s[pos] <='9'){ val = val*10+s[pos]-'0'; pos++; } tmp = makenode(val, negative); tmp->left = buildTree(); pos++; tmp->right = buildTree(); pos++; } else if(s[pos] == ')') return NULL; } return tmp; } void print_pre(node* root){ if(root != NULL){ cout << root->data << " "; print_pre(root->left); print_pre(root->right); } } void print_in(node* root){ if(root != NULL){ print_in(root->left); cout << root->data << " "; print_in(root->right); } } void print_post(node* root){ if(root != NULL){ print_post(root->left); print_post(root->right); cout << root->data << " "; } } void Find(node* root, int& M, int curSum){ if(root == NULL) return; curSum += root->data; if(root->left == NULL && root->right == NULL && curSum > M) M = curSum; Find(root->left, M, curSum); Find(root->right, M, curSum); } int FindMaxPathSum(node* root){ if(root == NULL) return 0; MaxSum = INT_MIN; Find(root, MaxSum, 0); return MaxSum; } // 0: protected // 1: no tower and not protected // 2: tower int dfs(node* root){ if(root == NULL) return 0; int l = dfs(root->left), r = dfs(root->right); if(l==1 || r==1){ num++; return 2; } if(l==2 || r==2) return 0; else return 1; } int BinaryTower(node* root){ if(root == NULL) return 0; if(dfs(root) == 1) num++; return num; } node* DeleteLeaf(node* root){ if(root == NULL) return NULL; if(root->left == NULL && root->right == NULL){ total -= root->data; delete root; return NULL; } root->left = DeleteLeaf(root->left); root->right = DeleteLeaf(root->right); return root; } bool check(node* a, node* b){ if(a == NULL && b == NULL) return true; if(a == NULL || b == NULL) return false; return (check(a->left, b->right) && check(a->right, b->left)); } bool Foldable(node* root){ if(root == NULL) return true; return check(root->left, root->right); } node* Invert(node* root){ if(root == NULL) return NULL; node *tmp = root->left; root->left = Invert(root->right); root->right = Invert(tmp); return root; } int Search(node* root, int& path){ if(root == NULL) return 0; int l = Search(root->left, path), r = Search(root->right, path); int curLeft, curRight; curLeft = curRight = 0; if(root->left != NULL && root->left->data == root->data) curLeft = l + 1; if(root->right != NULL && root->right->data == root->data) curRight = r + 1; path = max(path, curLeft+curRight); return max(curLeft, curRight); } int UnitedPath(node* root){ ans = 0; Search(root, ans); return ans; } int main(void){ string cmd; while(cin >> s){ pos = total = 0; node* root = buildTree(); while(cin >> cmd){ if(cmd == "Traverse"){ print_pre(root); cout << endl; print_in(root); cout << endl; print_post(root); cout << endl; } else if(cmd == "WeightSum") cout << total << endl; else if(cmd == "MaximumPathSum") cout << FindMaxPathSum(root) << endl; else if(cmd == "BinaryTower"){ num = 0; cout << BinaryTower(root) << endl; } else if(cmd == "Foldable"){ int ok = Foldable(root); if(ok) cout << "Yes" << endl; else cout << "No" << endl; } else if(cmd == "KingdomUnitedPath") cout << UnitedPath(root) << endl; else if(cmd == "DeleteLeaf") root = DeleteLeaf(root); else if(cmd == "Invert") root = Invert(root); else if(cmd == "End"){ cout << endl; break; } } } return 0; }
Editor is loading...