题目描述

官方描述(中文)
2021/09/24每日一题

思路

评论区的一条评论。


可以通过示例一看出，输出对应的不就是由1作为根节点，的二叉树的线序遍历输出吗。了解了这个特性，这个问题就简单许多了。只要对二叉树的先序遍历有一定了解就可以轻松胜任。扁平化多级链表相比于先序遍历二叉树困难点就在于如何处理根节点与其左右子节点的关系。我们可以把child看作left，把next看作right。

1. 先将root的next节点使用tempNext保存。
2. 之后如果root节点存在child节点就将child节点变成其next节点，将root的child节点置空。之后再通过对child节点进行递归操作，获取以child为root节点的链表对应的最后一个节点lastNode。(如果root节点的child节点为空，最后一个lastNode节点就是root节点)。
3. 得到最后一个节点lastNode，对lastNode和第一步保存的tempNext再做同样的操作，更新lastNode为以tempNext为root节点的链表对应的最后一个节点(如果root节点的next节点为空，最后一个lastNode节点就是root节点)。并返回lastNode。
4. 递归以上操作。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution 
{
public:
	Node* flatten(Node* head)
	{
		__Dfs(head);
		return head;
	}

private:
	Node* __Dfs(Node* head) 
	{
		if (!head)return nullptr;
		auto tempNext = head->next;
		decltype(head) lastNode = nullptr;
		if (head->child)
		{
			lastNode = __GetLastNode(head, head->child);
		}

		if (tempNext)
		{
			auto preNode = lastNode == nullptr ? head : lastNode;
			lastNode = __GetLastNode(preNode, tempNext);
		}

		return lastNode == nullptr ? head : lastNode;
	}	

	Node* __GetLastNode(Node* preNode, Node* nextNode)
	{
		if (!preNode || !nextNode)return nullptr;
		preNode->next = nextNode;
		preNode->next->prev = preNode;
		auto lastNode = __Dfs(preNode->next);
		preNode->child = nullptr;
		return lastNode;
	}
};

执行结果

Q.E.D.