跳至主要內容

114. 二叉树展开为链表


114. 二叉树展开为链表

🟠   🔖  深度优先搜索 链表 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

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 traversalopen in new window 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;
	}
};

相关题目

题号标题题解标签难度力扣
430扁平化多级双向链表[✓]深度优先搜索 链表 双向链表🟠🀄️open in new window 🔗open in new window
1660纠正二叉树 🔒 深度优先搜索 广度优先搜索 2+🟠🀄️open in new window 🔗open in new window