题意分析

本题要求根据输入的整数和以LISP S - 表达式表示的二叉树，判断该二叉树中是否存在一条从根节点到叶节点的路径，使得路径上节点的值之和等于给定的整数。对于空树，无论给定的整数是多少，都应输出 “no”。

解题思路

1. 数据结构定义

使用结构体 tree 来表示二叉树的节点，包含节点的值 data 以及左右子节点指针 left 和 right。

2. 输入处理

• 在 main 函数中，通过循环不断读取输入，每次读取一个整数 num 作为目标路径和。
• 接着读取LISP S - 表达式，将其存储在字符串 trees 中，同时使用变量 x 来记录括号的匹配情况，当 x 为 0 时表示一个完整的树表达式读取完毕。

3. 构建二叉树

• 定义 ft 函数来递归构建二叉树。从字符串 trees 中解析出节点的值，并递归构建左右子树。
• 解析节点值时，处理可能的负号，将字符转换为整数。
• 在构建过程中，同时计算从根节点到当前节点的路径和 sum。

4. 判断路径和

• 在 ft 函数中，当到达叶节点（即左右子节点都为空）时，检查当前路径和 sum 是否等于目标和 num，如果相等则将标志 flag 置为 1。

5. 释放内存

• 定义 del 函数，用于递归释放二叉树占用的内存，避免内存泄漏。

6. 输出结果

• 根据标志 flag 的值，输出 “yes” 或 “no”。

复杂度分析

时间复杂度

• 构建二叉树和遍历二叉树的过程都需要遍历字符串 trees 中的每个字符，因此时间复杂度为 $O(n)$，其中 $n$ 是字符串 trees 的长度。

空间复杂度

• 主要的空间开销在于递归调用栈和二叉树节点的存储，最坏情况下二叉树退化为链表，递归深度为树的节点数，因此空间复杂度为 $O(h)$，其中 $h$ 是二叉树的高度。

代码解释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>

using namespace std;

// 定义二叉树节点结构体
struct tree
{
    int data;
    tree *left, *right;
};

// 全局变量 m 用于记录字符串 trees 的当前位置
int m = 0;
// 存储 LISP S - 表达式的字符串
string trees = "";

// 递归释放二叉树内存的函数
void del(tree* &go)
{
    if(go != NULL)
    {
        if(go->left != NULL)
            del(go->left);
        if(go->right != NULL)
            del(go->right);
        delete go;
    }
    go = NULL;
}

// 递归构建二叉树并判断路径和的函数
void ft(tree *go, int all, int num, int &flag)
{
    // 处理左子树
    if(m + 1 < trees.size() && trees[m] == '(' && trees[m + 1] != ')')
    {
        tree *make = new tree;
        go->left = make;
        int u = m + 1, sum = 0, dis = 0;
        // 处理可能的负号
        if(trees[m + 1] == '-')
        {
            dis = 1;
            m++;
            u++;
        }
        // 解析节点值
        while(isdigit(trees[u]))
        {
            sum *= 10;
            sum += trees[u] - 48;
            u++;
            m++;
        }
        if(dis == 1)
            sum = -sum;
        make->data = sum;
        sum += all;
        m++;
        // 递归构建左子树
        ft(go->left, sum, num, flag);
    }
    else
    {
        go->left = NULL;
        m += 2;
    }

    // 处理右子树
    if(m + 1 < trees.size() && trees[m] == '(' && trees[m + 1] != ')')
    {
        tree* make = new tree;
        go->right = make;
        int u = m + 1, sum = 0, dis = 0;
        if(trees[m + 1] == '-')
        {
            dis = 1;
            m++;
            u++;
        }
        while(isdigit(trees[u]))
        {
            sum *= 10;
            sum += trees[u] - 48;
            u++;
            m++;
        }
        if(dis) sum = -sum;
        sum += all;
        m++;
        // 递归构建右子树
        ft(go->right, sum, num, flag);
    }
    else
    {
        go->right = NULL;
        m += 2;
    }

    m++;
    // 判断是否为叶节点且路径和等于目标和
    if(go->left == NULL && go->right == NULL && all == num)
        flag = 1;
}

int main()
{
    int num;
    while(cin >> num)
    {
        string mu;
        trees = "";
        m = 0;
        int flag = 0;
        // 创建根节点
        tree *go = new tree;
        go->left = go->right = NULL;
        char ch;
        int x = 0;
        // 读取 LISP S - 表达式
        while(cin >> ch)
        {
            if(ch != ' ')
                trees += ch;
            if(ch == '(') x++;
            if(ch == ')') x--;
            if(x == 0) 
            {
                break;
            }
        }
        // 构建二叉树并判断路径和
        ft(go, 0, num, flag);
        // 释放二叉树内存
        del(go);
        if(flag)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}