2019.10.17 문제 요약

세 개의 검지 offer, 한 개의 Leet Code.
1. 위에서 아래로 두 갈래 나무를 인쇄한다.
두 갈래 나무의 차원이 두루 흐르고 넓이가 우선적으로 검색되며 대기열로 해결됩니다.

vector PrintFromTopToBottom(TreeNode* root) {
        vectorres;
        if(!root)
        {
            return res;
        }
        queueq;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* node=q.front();
            q.pop();
            res.push_back(node->val);
            if(node->left)
            {
                q.push(node->left);
            }
            if(node->right)
            {
                q.push(node->right);
            }
        }
        return res;
    }

2. 어떤 수조가 두 갈래 검색 트리의 후속적인 역행을 할 수 있는지 판단한다.
a:두 갈래 검색 트리, 뿌리 노드의 값은 왼쪽 트리보다 크고 오른쪽 트리보다 작습니다.
b:뒷차례 두루 다니다 좌우 뿌리.
c:매번 수조의 마지막 위치에서 루트 노드를 가져옵니다. 이동 후 루트 노드보다 큰 첫 번째 값을 반복해서 찾습니다. 이 값은 앞으로 왼쪽 나무이고 뒤로 오른쪽 나무입니다.
오른쪽 트리에 노드가 뿌리 노드보다 작으면 두 갈래로 트리의 후속 경로를 검색할 수 없습니다.그렇지 않으면 좌우 나무를 계속 판단하게 된다.

bool VerifySquenceOfBST(vector sequence) {
        int n=sequence.size();
        if(n<=0)
        {
            return false;
        }
        int root=sequence[n-1];
        int i=0;
        for(;iroot)
            {
                break;
            }
        }
        int j=i;
        for(;j0)
        {
            vectorleftvec;
            leftvec.assign(sequence.begin(),sequence.begin()+i);
            left=VerifySquenceOfBST(leftvec);
        }
        bool right=true;
        if(irightvec;
            rightvec.assign(sequence.begin()+i,sequence.end()-1);
            right=VerifySquenceOfBST(rightvec);
        }
        return left&&right;
    }

3. 두 갈래 트리의 모든 경로와 값을 위한 경로를 인쇄합니다.
차례로만약에 현재 노드의 값이 기대치와 같고 현재 노드가 잎 노드라면 이 경로를 결과에 눌러 넣는다. 그렇지 않으면 왼쪽 나무가 비어 있지 않고 왼쪽 나무, 오른쪽 나무가 비어 있지 않고 오른쪽 나무를 판단한다.마지막으로 귀속이 끝날 때마다 현재 눌린 노드를 삭제해야 합니다.교묘한 처리는 매번 기대치를 현재 기대치와 현재 노드 값의 차이로 분류하는 것이다.

vector>result;
    vectorres;
    vector > FindPath(TreeNode* root,int expectNumber) {
        if(!root)
        {
            return result;
        }
        res.push_back(root->val);
        if(root->val==expectNumber&&root->left==nullptr&&root->right==nullptr)
        {
            result.push_back(res);
        }
        if(root->left)
        {
            result=FindPath(root->left,expectNumber-root->val);
        }
        if(root->right)
        {
            result=FindPath(root->right,expectNumber-root->val);
        }
        if(res.size()>0)
        {
            res.pop_back();
        }
        return result;
    }

4. 체인 테이블에 고리가 있는지, 빈 바늘이 없는지, 반환 고리의 입구 노드가 있는지 판단한다.
a:사고방식은 두 개의 빠른 바늘을 준비하는 것이다. 느린 바늘과 빠른 바늘이 같을 때 고리가 있다는 것을 설명한다. 만약에 반복하는 과정에서 빠른 바늘이 비어 있다면 고리가 없다는 것을 설명하고 빈으로 돌아간다.그리고 느린 바늘을 다시 머리 결점으로 복제하고 두 바늘은 한 걸음 한 걸음 걷다가 다시 만나면 링 입구다.
b:몇 가지 사항을 주의하십시오. 만약에 머리 결점이 비어 있거나 노드가 하나만 있으면 고리가 없습니다.스피드 바늘이 처음 반복될 때, 스피드 바늘이나 스피드 바늘의 다음 바늘이 비어 있으면 모두 비어 있어야 한다.

ListNode *detectCycle(ListNode *head) {
        if(!head||!head->next)
        {
            return nullptr;
        }
        ListNode *slow=head;
        ListNode *fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(!fast||!fast->next)
            {
                return nullptr;
            }
            if(slow==fast)
            {
                break;
            }
        }
        slow=head;
        while(slow!=fast)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }