114. 二叉树展开为链表

🟠   🔖  栈 树 深度优先搜索 链表 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]

Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [0]

Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

题目大意

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解题思路

思路一：迭代

使用一个栈来模拟先序遍历。从根节点开始，将右子节点和左子节点入栈。出栈时，将当前节点的右子节点指向栈顶节点，同时将左子节点设为 null，以满足展开的要求。不断重复这个过程，直到栈为空，即完成了二叉树的展开。展开后的链表即为二叉树的先序遍历结果。

---

思路二：递归

通过递归先展开左右子树，然后将根节点的右子树连接到已经展开的左子树的末尾。

代码

迭代

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
	if (!root) return null;
	let stack = [root];
	while (stack.length) {
		let node = stack.pop();
		if (node.right) stack.push(node.right);
		if (node.left) stack.push(node.left);
		node.left = null;
		node.right = stack[stack.length - 1] || null;
	}
};

递归

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
	if (!root) return null;

	flatten(root.left);
	flatten(root.right);

	let rightSubtree = root.right;
	root.right = root.left;
	root.left = null;

	let end = root;
	while (end.right) {
		end = end.right;
	}
	end.right = rightSubtree;
};

相关题目

题号	标题	题解	标签	难度
430	扁平化多级双向链表	[✓]	深度优先搜索 链表 双向链表
1660	纠正二叉树 🔒		树 深度优先搜索 广度优先搜索 2+