N-叉树--遍历N-叉树所有从顶点到叶子节点的路径

Shopee的Orange Day

Shopee每个月都有属于大家的节日，每到这个时候，大家都会穿着橙色的T恤，吃着水果蛋糕，做着游戏。瞧，今天又是Orange Day了，吃货小虾同学早早的来到现场，看看有没有什么吃的，刚刚走进去就发现我们的前台mm愁眉苦脸的看着挂满礼物的发财树，细看发现，发财树的树枝因为承重不均，东倒西歪。是时候展现真正的技术啦，小虾同学，马上走上去，让前台mm把挂礼物的方案拿出来，前台mm拿出一大叠方案，小虾同学顿时傻眼了，但是他马上想到了一个方法，写一个程序判断每种方案的承重误差，把不合格的都干掉就行了。经过分析，把发财树抽象为一颗树。只要发财树的从顶部到各个叶子的各个路径上面的最大最小重量的差值在方案的误差范围内，就可以正常承重。

输入第一行表示数据样例数T，表示接下来会有T个相同格式的样例输入

每个样例输入如下

输入的第一行输入 n,（2 ≤ n ≤ 100000，节点的编号为0到n-1,0为根节点）组成，

第二行有 n 个数，表示每个节点挂的礼物的重量 w（1<= w<= 1000）
下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出最大差值。

#include<iostream>
#include<vector>
using namespace std;

struct Node{
    int val;
    vector<int> childs;
    Node(){
        this->val = -1;
    }
    Node(int val){
        this->val = val;
    }
};

void dfs(vector<int>& Path,int CurrentNodeIndex,const vector<Node>& tree,vector<int>& MaxPath){
    Path.push_back(CurrentNodeIndex);
    if(!tree[CurrentNodeIndex].childs.empty()){
        for(int i = 0;i < tree[CurrentNodeIndex].childs.size();i ++){
            dfs(Path,tree[CurrentNodeIndex].childs[i],tree,MaxPath);
        }
    }
    else{
        int MAX = 0;
        int MIN = 0x3f3f3f3f;
        for(int i = 0;i < Path.size();i ++){
            int Index = Path[i];
            MAX = max(MAX,tree[Index].val);
            MIN = min(MIN,tree[Index].val);
        }
        MaxPath.push_back(MAX - MIN);
    }
    Path.pop_back();
}

int main(){
    int n;int MAX = 0;
    scanf("%d",&n);
    vector<Node> tree(n);
    for(int i = 0;i < n;i ++){
        int tmp;
        scanf("%d",&tmp);
        tree[i].val = tmp;
    }
    for(int i = 0;i < n - 1;i ++){
        int father,son;
        scanf("%d%d",&father,&son);
        tree[father].childs.push_back(son);
    }
    vector<int> Path;
    vector<int> Result;
    dfs(Path,0,tree,Result);
    for(int i = 0;i < Result.size();i ++){
        MAX = max(MAX,Result[i]);
    }
    printf("%d\n",MAX);
    return 0;
}