leetcode每日一题

3/24

128 最长连续序列

本题基本的算法思想是并查集与哈希表
len[i]存储数字i所在的最长连续序列，但其实无需将所有的数字都更新为序列长度，每次只需更新左右两个端点的数字即可。
每次遍历一个数，若曾经出现过，则跳过。若没有出现过，则令其与左右两边的集合合并，令新长度为len[i-1]+len[i+1]+1，更新左右两个端点和len[i]的值。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        map<int,int> len;
        int max_len=0,cur_len;
        for(int i=0;i<nums.size();++i){
            if(len[nums[i]]==0){
                cur_len=len[nums[i]-1]+len[nums[i]+1]+1;
                len[nums[i]]=cur_len;
                len[nums[i]-len[nums[i]-1]]=cur_len;
                len[nums[i]+len[nums[i]+1]]=cur_len;
                max_len=max(max_len,cur_len);
            }
        }
        return max_len;
    }
};

3/25

200 岛屿的个数

图的连通分量问题，我用dfs解决，评论区里也有用并查集的
并查集的find函数融合了查找和集合合并

dfs:

class Solution {
public:
    void dfs(vector<vector<bool>>& vis,vector<vector<char>> &grid,int x,int y){
        vis[x][y]=true;
        for(int i=-1;i<=1;++i){
            for(int j=-1;j<=1;++j){
                if((i+j==1||i+j==-1)&&x+i>=0&&x+i<grid.size()&&y+j>=0&&y+j<grid[0].size()){
                    if(grid[x+i][y+j]=='1'&&!vis[x+i][y+j]){
                        dfs(vis,grid,x+i,y+j);
                    }
                }
            }
        }
    } 
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0)return 0;
        int raws=grid.size(),cols=grid[0].size(),cnt=0;
        vector<vector<bool>> vis(raws,vector<bool>(cols,0));
        for(int i=0;i<raws;++i){
            for(int j=0;j<cols;++j){
                if(grid[i][j]=='1'&&!vis[i][j]){
                    dfs(vis,grid,i,j);
                    cnt++;
                } 
            }
        }
        return cnt;
    }
};

并查集:

class Solution {
public:
    vector<int> pre;
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);//更新x的父亲，压缩路径
        return pre[x];
    }
    int numIslands(vector<vector<char>>& grid) {
        int rows=grid.size();
        if(rows==0)return 0;
        int cols=grid[0].size();
        for(int i=0;i<rows*cols;++i)pre.push_back(i);
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                int id=i*cols+j,rep;
                if(grid[i][j]=='0'){
                    pre[id]=-1;//若为海，则父亲为-1
                    continue;
                }
                //更新边角的“1”为新的父亲节点
                if(i>0&&grid[i-1][j]=='1'){
                    rep=(i-1)*cols+j;
                    pre[find(id)]=find(rep);
                }
                if(j>0&&grid[i][j-1]=='1'){
                    rep=i*cols+j-1;
                    pre[find(id)]=find(rep);
                }
            }
        }
        map<int,bool> hs;
        int cnt=0;
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                int id=i*cols+j;
                if(grid[i][j]=='1'&&hs[find(id)]==false){
                    hs[find(id)]=true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

3/26

684 冗余连接

并查集

class Solution {
public:
    int pre[1010];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void merge(int a,int b){
        pre[a]>pre[b]?pre[a]=pre[b]:pre[b]=pre[a];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> e(2,-1);
        for(int i=1;i<=edges.size();++i){
            pre[i]=i;
        }
        for(int i=0;i<edges.size();++i){
            int p1=find(edges[i][0]);
            int p2=find(edges[i][1]);
            if(p1==p2){
                e[0]=edges[i][0],e[1]=edges[i][1];//若两个相连节点的父节点相同，即在同一个集合内，则这条边可去
            }
            merge(p1,p2);
        }
        return e;
    }
};

3/27

721 账户合并

这个代码能不能过要看运气，多提交几次就过了
要将一个个账户抽象为一个个独立的集合，用哈希表进行映射
然后使用并查集算法

class Solution {
public:
    int pre[1010];
    int find(int x){
        return x!=pre[x]?pre[x]=find(pre[x]):x;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
    void unit(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return;
        pre[a]=b;
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int num=accounts.size();
        for(int i=0;i<num;++i){
            pre[i]=i;
        }//init
        for(int i=0;i<num;++i){
            for(int j=0;j<i;++j){
                if(accounts[i][0]==accounts[j][0]&&!same(i,j)){//same name
                    bool flag=false;
                    for(int k=1;k<accounts[i].size()&&!flag;++k){
                        for(int t=1;t<accounts[j].size()&&!flag;++t){
                            if(accounts[i][k]==accounts[j][t]){
                                unit(i,j);
                                flag=true;
                            }
                        }
                    }
                }  
            }
        }
        
        vector<set<string> > res(num);//使用set可以去除冗余email并且按字典序排序
        for(int i=0;i<num;++i){
            pre[i]=find(i);
            for(int j=1;j<accounts[i].size();++j)
                res[pre[i]].insert(accounts[i][j]);
        }//union accounts
        vector<vector<string> > ans; 
        for(int i=0;i<num;++i){
            if(pre[i]==i){
                vector<string> one;
                one.push_back(accounts[i][0]);
                for(auto email:res[i]){
                    one.push_back(email);
                }
                ans.push_back(one);
            }//未被合并的集合,加入到ans中
        }
        return ans;
    }
};

3/28

924 尽量减少恶意软件传播

并查集

class Solution {
public:
    int pre[310];
    int vir[310];
    int num[310];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p2]=p1;
    }
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        sort(initial.begin(),initial.end());
        int nodes=graph.size();
        for(int i=0;i<nodes;++i){
            pre[i]=i;
        }
        for(int i=0;i<nodes;++i){
            for(int j=i+1;j<nodes;++j){
                if(graph[i][j]){
                    unit(i,j);
                }
            }
        }
        for(int i=0;i<nodes;++i){
            int x=find(i);
            num[x]++;
        }
        for(int i=0;i<initial.size();++i){
            int x=find(initial[i]);
            vir[x]++;
        }
        int index=-1,les=0;
        for(int i=0;i<initial.size();++i){
            if(vir[pre[initial[i]]]==1&&num[pre[initial[i]]]>les){
                index=initial[i];
                les=num[pre[initial[i]]];
            }
            //cout<<num[pre[initial[i]]]<<" "<<initial[i]<<" "<<pre[initial[i]]<<endl;
        }
        return index==-1?initial[0]:index;
    }
};

3/29

947 移除最多同行或同列石头

图的连通分量问题，并查集即可解决
移除的最多的石头数目=坐标点的数目-集合数目

class Solution {
public:
    int pre[1010];
    bool num[1010];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p1]=p2;
    }
    int removeStones(vector<vector<int>>& stones) {
        fill(num,num+1010,0);
        for(int i=0;i<stones.size();++i){
            pre[i]=i;
        }
        for(int i=1;i<stones.size();++i){
            for(int j=0;j<i;++j){
                if(stones[i][0]==stones[j][0]||stones[i][1]==stones[j][1]){
                    unit(i,j);
                }
            }
        }
        int cnt=0;
        for(int i=0;i<stones.size();++i){
            if(!num[find(i)]){
                num[find(i)]=true;
                cnt++;
            }
        }
        return stones.size()-cnt;
    }
};

3/30

990 等式方程的可满足性

并查集，相等的变量放在一个集合里，然后遍历所有的!=，如果发现某一组的变量在一个集合中，return false

class Solution {
public:
    int pre[1000];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p1]=p2;
    }
    int charToNum(char x){
        return x-'a';
    }
    bool equationsPossible(vector<string>& equations) {
        for(int i=0;i<100;++i){
            pre[i]=i;
        }
        for(int i=0;i<equations.size();++i){
            if(equations[i][1]=='='){
                unit(charToNum(equations[i][0]),charToNum(equations[i][3]));
            }
        }
        for(int i=0;i<equations.size();++i){
            if(equations[i][1]=='!'){
                if(find(charToNum(equations[i][0]))==find(charToNum(equations[i][3]))){
                    return false;
                }
            }
        }
        return true;
    }
};

160 相交链表

先将遍历两个链表，使两者等长，再一起遍历

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int num1=1,num2=1;
        bool flag=true;
        if(headA==NULL||headB==NULL)return NULL;
        ListNode* a=headA;
        ListNode* b=headB;
        while(a->next!=NULL){
            num1++;
            a=a->next;
        }
        while(b->next!=NULL){
            num2++;
            b=b->next;
        }
        if(num1<num2)flag=false;
        if(flag){
            for(int i=0;i<num1-num2;++i){
                headA=headA->next;
            }
        }else{
            for(int i=0;i<num2-num1;++i){
                headB=headB->next;
            }
        }
        while(headA&&headB&&headA!=headB){
            headA=headA->next;
            headB=headB->next;
        }
        return headA;
    }
};

拓扑排序：用于DAG（有向无环图）

拓扑排序是一个有向无环图的线性排列，每个顶点有且仅出现一次，若一个顶点存在A到B的路径，则排序中A一定在B前面
写出一个图的拓扑排序方法：选定一个没有前驱节点的起点，删除这个节点并不断递归的寻找以它为起点的有向边，直到图为空或者没有无前驱的节点为止，后面的情况说明这个图必存在环。并且一个DAG的拓扑排序可能有多个。

207 课程表

课程表使用bfs实现的拓扑排序，判断是否存在环
主要有三步：
1.初始化所有节点的度
2.将度为0的节点入队
3.bfs,将访问过的节点设为-1表示删除，将所有相连的节点的度减一，将度为0的节点入队

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> indegree(numCourses,0);//前度数组
        for(int i=0;i<prerequisites.size();++i){
            auto course=prerequisites[i];
            indegree[course.first]++;
        }
        queue<int> zeros;
        for(int i=0;i<numCourses;++i){
            if(indegree[i]==0)zeros.push(i);
        }
        int cnt=0;
        while(!zeros.empty()){
            cnt++;
            int node=zeros.front();
            zeros.pop();
            indegree[node]=-1;//删除的节点置为-1
            for(int i=0;i<prerequisites.size();++i){
                auto temp=prerequisites[i];
                if(temp.second==-1)continue;
                if(temp.second==node){
                    indegree[temp.first]--;
                    if(indegree[temp.first]==0){
                        zeros.push(temp.first);
                    }
                }
            }
        }
        return cnt==numCourses;
    }
};

3/31

210 课程表II

拓扑排序

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> indegree(numCourses,0);
        vector<int> ans,emp;
        for(int i=0;i<prerequisites.size();++i){
            indegree[prerequisites[i].first]++;
        }//初始化所有节点的度
        queue<int> zeros;
        for(int i=0;i<numCourses;++i){
            if(indegree[i]==0)zeros.push(i);
        }//将度为0的节点入队
        while(!zeros.empty()){
            int node=zeros.front();
            zeros.pop();
            ans.push_back(node);
            indegree[node]=-1;
            for(int i=0;i<prerequisites.size();++i){
                auto temp=prerequisites[i];
                if(temp.second==node){
                    if(--indegree[temp.first]==0)zeros.push(temp.first);
                }
            }
        }
        return ans.size()==numCourses?ans:emp;
    }
};

997 找到小镇的法官

法官的入度应该为N-1，出度应该为0

class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) {
        vector<bool> isTrust(N+1,true);
        vector<int> num(N+1,0);
        for(int i=0;i<trust.size();++i){
            isTrust[trust[i][0]]=false;
            num[trust[i][1]]++;
        }
        int index=-1;
        for(int i=1;i<N+1;++i){
            if(isTrust[i]&&num[i]==N-1)index=i;
        }
        return index;
    }
};

4/1

42 接雨水

维护一个单调递减栈，当出现一根柱子大于save.top()时记录其值并pop，如果此时栈为空，则无法接雨水，退出循环，否则取最小高度乘以x方向上的距离

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> save;
        int num=0,floor=0;
        for(int i=0;i<height.size();++i){
            while(!save.empty()&&height[save.top()]<=height[i]){
                floor=height[save.top()];
                save.pop();
                if(save.empty())break;
                num+=(min(height[save.top()],height[i])-floor)*(i-save.top()-1);
            }
            save.push(i);
        }
        return num;
    }
};

4/2

84 柱状图中的最大矩形

单调栈问题，维持一个递增的单调栈,当有小的数出现时不断pop，但是这样无法处理最后一根柱子，所以一开始要给数组最后加一个长度为0的柱子。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        stack<int> st;
        int area=0;
        for(int i=0;i<heights.size();++i){
            while(!st.empty()&&heights[st.top()]>heights[i]){
                int k=st.top();
                st.pop();
                area=max(area,heights[k]*(st.empty()?i:(i-st.top()-1)));
            }
            st.push(i);
        }
        return area;
    }
};

4/4

15 三数之和

用三个指针i,j,k 使得nums[i]+nums[j]=-nums[k]，将三数之和转化为两数之和，可以用双指针法解决问题。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans; 
        if(nums.size()<3) return ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;++i){
            int l=i+1,r=nums.size()-1;
            while(l<r&&(i==0||(i>0&&nums[i]!=nums[i-1]))){
                while(r>l&&nums[l]+nums[r]!=-nums[i]){
                if(nums[l]+nums[r]>-nums[i])r--;
                    else l++;
                }
                if(r>l&&nums[l]+nums[r]==-nums[i]){
                    ans.push_back({nums[i],nums[l],nums[r]});
                    while(r>l&&nums[l]==nums[l+1])l++;
                    while(r>l&&nums[r]==nums[r-1])r--;
                    l++;
                }
            } 
        }
        return ans;
    }
};

4/5

16 最接近的三数之和

与15相似，双指针法

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int inf=100000;
        int ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;++i){
            int j=i+1,k=nums.size()-1;
            while(j<k){
                while(abs(nums[i]+nums[j]+nums[k]-target)>inf&&j+1<k){
                    if(nums[i]+nums[j]+nums[k]-target<0)j++;
                    else k--;
                }
                //cout<<i<<" "<<j<<" "<<k<<" "<<ans<<endl;
                if(abs(nums[i]+nums[j]+nums[k]-target)<inf){
                    inf=abs(nums[i]+nums[j]+nums[k]-target);
                    ans=nums[i]+nums[j]+nums[k];
                }
                if(nums[i]+nums[j]+nums[k]-target<0)j++;
                else k--;
            }
        }
        return ans;
    }
};

4/6

3 无重复字符的最长字串

最重要的一步是用哈希表存储每个字符最后出现的位置

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=0;
        int m[256]={0};
        int res=0;
        for(int i=0;i<s.size();++i){
            if(left>m[s[i]]||m[s[i]]==0){
                res=max(res,i-left+1);
            }else{
                left=m[s[i]];
            }
            m[s[i]]=i+1;
        }
        return res;
    }
};

4/8

338 比特位计数

关于计数的小技巧:i&(i-1)可以去掉二进制的i最右边的1，由于去掉之后的数比i小，所以可以用之前算出来的加1得到。
同样，i>>1可以将1向右移一位，得到的值同样比i小，如果最右边有1，则加上1，没有则不加，可以用res[i>>1]+(i&1)
算数运算 > 移位运算 > 位运算 > 逻辑运算，所以一定要加括号

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        for(int i=1;i<=num;++i){
            res[i]=res[i&(i-1)]+1;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        for(int i=1;i<=num;++i){
            res[i]=res[i>>1]+(i&1);
        }
        return res;
    }
};

4/9

1011 在D天内送达包裹的能力

二分法，最小化可行的值，注意C(l)永远是false，所以要返回r

class Solution {
public:
    bool C(int x,int D,vector<int>& weights){
        int j=0;
        for(int i=0;i<D;++i){
            int t=x;
            while(j<weights.size()&&t>=weights[j]){
                t-=weights[j++];
            }
            if(j==weights.size())return true;
        }
        return false;
    }
    int shipWithinDays(vector<int>& weights, int D) {
        int r=100000,l=1,mid;
        while(l+1!=r){
            mid=(r+l)/2;
            if(C(mid,D,weights)){
                r=mid;
            }else{
                l=mid;
            }
            //cout<<l<<" "<<r<<" "<<mid<<endl;
        }
        return r;
    }
};

4/10

528 按权重随机选择

class Solution {
private:
    vector<int> weight;
    vector<int> sum;
public:
    int random(int x){
        return rand()%(x);
    }
    Solution(vector<int>& w) {
        weight=w;
        if(w.size()>0)sum.push_back(w[0]);
        for(int i=1;i<w.size();++i)sum.push_back(w[i]+sum[i-1]);
    }
    bool C(int mid,int choose){
        return sum[mid]>=choose;
    }
    int pickIndex() {
        int choose=random(sum.back());
        int l=0,r=sum.size()-1;
        while(l<r-1){
            int mid=(r+l)/2;
            if(C(mid,choose))r=mid;
            else l=mid;
        }
        if(choose<sum[l])return l;
        return r;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

或者直接用stl里的upper_bound()

class Solution {
public:
    Solution(vector<int> w) {
        sum=vector<int>(w.size(),0);
        if(sum.size()>0)sum[0]=w[0];
        for(int i=1;i<w.size();i++) sum[i]=sum[i-1]+w[i];
    }
    
    int pickIndex() {
        int x=rand()%sum.back();
        int pos=upper_bound(sum.begin(),sum.end(),x)-sum.begin();
        return pos;
    }
 
private:
    vector<int> sum;
};

4/11

575 分糖果

哈希表或者set

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        map<int,bool> hst;
        int cnt=0;
        for(int i=0;i<candies.size();++i){
            if(!hst[candies[i]]){
                hst[candies[i]]=true;
                cnt++;
            }
        }
        return min(cnt,int(candies.size()/2));
    }
};

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        int n = candies.size()/2;
        set<int> intS(candies.begin(), candies.end());
        return min((int)intS.size(), n);
    }
};

4/12

17 电话号码的字母组合

暴力搜就完事

class Solution {
public:
    vector<string> ans;
    map<char,string> hst;
    void dfs(string digits,int depth,string res){
        if(depth==digits.size()){
            ans.push_back(res);
            return;
        }
        for(int i=0;i<hst[digits[depth]].size();++i){
            dfs(digits,depth+1,res+hst[digits[depth]][i]);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)return ans;
        hst['2']="abc";
        hst['3']="def";
        hst['4']="ghi";
        hst['5']="jkl";
        hst['6']="mno";
        hst['7']="pqrs";
        hst['8']="tuv";
        hst['9']="wxyz";
        dfs(digits,0,"");
        return ans;
    }
};

4/14

292 Nim game

一道博弈论，如果取一块石头，赢。
取两块石头，赢。
三块石头，赢。
四块石头，输。
五块石头

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4)return true;
        return false;
    }
};

4/15

747 至少是其他数字两倍的最大数

今天偷懒做水题

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int first_max=0,second_max=0,max_index=-1;
        for(int i=0;i<nums.size();++i){
            if(nums[i]>first_max){
                second_max=first_max;
                first_max=nums[i];
                max_index=i;
            }else if(nums[i]>second_max){
                second_max=nums[i];
            }
        }
        return first_max>=(second_max<<1)?max_index:-1;
    }
};

4/16

319 灯泡开关

首先翻译一下题目，即求1~n中因子是奇数的数的个数，若一个数的因子是奇数，它的充要条件是它是个完全平方数，简要证明：非完全平方数的因子都是成对出现，例如10：1，10 2，5，而完全平方数除了成对出现的因子外还存在它开方的数：如16：1，16 2，8 4，4。
而判断一个数是否是完全平方数，只需将它开方取证再平方，观察它与原来的值是否相等。而A~B中的完全平方数个数就是B的平方数个数减去A的平方数个数。一个数从1~A中的平方数个数为 $floor(sqrt(A))$

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

4/17

349 两个数组的交集

双指针

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        if(nums1.empty()||nums2.empty()) return ans;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        map<int,bool> isok;
        int ptr=0;
        for(int i=0;i<nums1.size();++i){
            while(ptr<nums2.size()&&nums2[ptr]<nums1[i])ptr++;
            if(ptr<nums2.size()&&nums2[ptr]==nums1[i]&&!isok[nums1[i]]){
                isok[nums1[i]]=true;
                ans.push_back(nums1[i]);
                ptr++;
            }
        }
        return ans;
    }
};

4/18

590 N叉树的后序遍历

DFS+回溯即可

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> ans;
    void dfs(Node* node){
        if(node==NULL)return;
        for(int i=0;i<node->children.size();++i)dfs(node->children[i]);
        ans.push_back(node->val);
    }
    vector<int> postorder(Node* root) {
        dfs(root);
        return ans;
    }
};

589 N叉树的前序遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> ans;
    void dfs(Node* node){
        if(node==NULL)return;
        ans.push_back(node->val);
        for(int i=0;i<node->children.size();++i)dfs(node->children[i]);
    }
    vector<int> preorder(Node* root) {
        dfs(root);
        return ans;
    }
};