题解：P1001 A+B Problem

· · 题解

P1001 A+B Problem

0.前言

什么，可以发题解了？

必须来一波！

1.问题转化

不妨用DFS序。

创建一个虚拟的二叉树，其中左子节点代表A，右子节点代表B。使用DFS遍历这棵树，在遍历过程中累加节点的值即可。

2.代码

#include<bits/stdc++.h>
using namespace std;
//树节点结构
struct Tree
{
    int val;
    Tree* left;
    Tree* right;
    Tree(int x):val(x),left(nullptr),right(nullptr) {}
};
//DFS序
int dfsSum(Tree* root) 
{
    if(!root) return 0;
    stack<Tree*> s;
    s.push(root);
    int sum=0;
    while(!s.empty()) 
    {
        Tree* node=s.top();
        s.pop();
        sum+=node->val;
        if(node->right) s.push(node->right);
        if(node->left) s.push(node->left);
    }
    return sum;
}
int main() 
{
    int a,b;
    cin>>a>>b;
    //创建虚拟树结构
    Tree* root=new Tree(0);//虚拟根节点
    root->left=new Tree(a);//左子节点存储a
    root->right=new Tree(b);//右子节点存储b
    // 使用DFS序计算和
    int ans=dfsSum(root)-root->val;  // 减去虚拟根节点的值
    cout<<ans<<endl;
    return 0;
}