做网站的公司 成都/百度推广登陆入口官网

题目

OJ平台

解题概述

看了这个扁平化实现的简介，第一时间就能想到用深搜，但注意还要实现对尾部连接，这个我是想到用栈存储然后再处理的方式，官方题解就是一次递归就解决了。

解题代码

//一看就老深搜了
class Solution {
public:stack<Node*>St; //用栈记录下没有被处理的结点Node* rear = nullptr; //记录尾指针Node* flatten(Node* head) {if(!head)return nullptr;Node* res = dfs(head);handle_r();return res;}Node* dfs(Node* head){if(head->next==nullptr&&head->child==nullptr){//无法往下走的情况rear = head;}else if(head->child){//有下一层级的情况if(head->next)St.push(head->next);Node* child = head->child;child->prev = head;head->child = nullptr;head->next = dfs(child);}else {//层级为1的情况head->next = dfs(head->next);}return head;}//根据记录的尾指针进行连接void handle_r(){Node* r = rear;while(!St.empty()){Node* p = St.top();St.pop();p->prev = r;r->next = p;if(St.empty())break;while(p->next){p = p->next;}r = p;}}
};