华为机试
为啥华为机试越来越难了？？😐是因为今年疫情原因招的少还是大环境裁员呀？
记得去年的机试题，三题中有两题是leecode原题，今年这。。23届好难😑😑
---补第二题：按照路径替换二叉树---
/** -*- encoding: utf-8 -*-
Description :按照路径替换二叉树
Version :1.0
*/
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct Node
{
int value;
Node *left;
Node *right;
Node(int val)
{
value = val;
left = NULL;
right = NULL;
}
};
Node *nums2Tree(int index, vector<int> &nums);
int main()
{
vector<int> nums;
char ch;
int n;
while (scanf("%d", &n) != EOF)
{
nums.push_back(n);
ch = getchar();
if (ch != ',')
{
break;
}
}
string str;
cin >> str;
vector<int> path;
for (int i = 0; i < str.size(); i++)
{
if (isdigit(str[i]))
{
path.push_back(str[i] - '0');
}
}
vector<int> new_nums;
while (scanf("%d", &n) != EOF)
{
new_nums.push_back(n);
ch = getchar();
if (ch != ',')
{
break;
}
}
Node *old_node = nums2Tree(0, nums);
Node *new_node = nums2Tree(0, new_nums);
Node *curNode = old_node;
if (curNode->value != path[0])
{
cout << -1 << endl;
return 0;
}
Node *preNode = curNode;
int flag = 0;
for (int i = 1; i < path.size(); i++)
{
int num = path[i];
if (num == curNode->left->value)
{
flag = 1;
preNode = curNode;
curNode = curNode->left;
}
else if (num == curNode->right->value)
{
flag = 2;
preNode = curNode;
curNode = curNode->right;
}
}
if (flag == 0)
{
old_node = new_node;
}
else if (flag == 1)
{
preNode->left = new_node;
}
else if (flag == 2)
{
preNode->right = new_node;
}
queue<Node *> q;
q.push(old_node);
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
Node *cur = q.front();
q.pop();
if (cur->value != 0)
{
cout << cur->value << ",";
}
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
{
q.push(cur->right);
}
}
}
return 0;
}
Node *nums2Tree(int index, vector<int> &nums)
{
Node *root = new Node(nums[index]);
if (2 * index + 1 < nums.size())
{
root->left = nums2Tree(2 * index + 1, nums);
}
if (2 * index + 2 < nums.size())
{
root->right = nums2Tree(2 * index + 2, nums);
}
return root;
}
