//单链表的反转
struct LinkNode{
LinkNode * next;
int val;
};

LinkNode * ReverseList(LinkNode * head){
    if(head == nullptr) return head;
    LinkNode * Newhead; 
    LinkNode * pre = nullptr;
    LinkNode * pcur = head;
    while(pcur){
        LinkNode * Next = pcur->next;
        pcur->next = pre;
        pre = pcur;
        pcur = Next;
    } 
    Newhead = pre;
    return Newhead; 
}

//二叉树 找到最深的叶子结点 左子树是0，右子树是1

struct TreeNode{
    TreeNode* left;
    TreeNode * right;
    int val;
};
void DFS_deep(TreeNode * root,int deep);
void DFS(TreeNode * root,string target,int deep);

int Deep = 0;
vector<string>Res;

vector<string> main(TreeNode * root){
    if(root == nullptr) return "";
    //计算深度
    DFS_deep(root,0);
    //找到深度为最深的，从根结点到叶子结点的路径
    DFS(root,"",0);
    return Res;
}

void DFS_deep(TreeNode * root,int deep){
    if(root == nullptr) return;
    deep++;
    Deep = max(Deep,deep);
    DFS_deep(root->left,deep);
    DFS_deep(root->right,deep);
}

void DFS(TreeNode * root,string target,int deep){
    if(deep == Deep) {
        Res.push_back(target);
        return;
    }
    if(root == nullptr) return target;
    string Ori = target;
    if(root->left) {
        Ori += '0';
        DFS(root->left,Ori,++deep);
    }
    if(root->right) {
        Ori += '1';
        DFS(root->right,Ori,++deep);
    }
}