华为机试

/** -*- 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;
}